Huffman-i tərsinə çevirmək
Statik Huffman kodlaşdırması, əsasən mətn sıxışdırılması üçün istifadə olunan bir kodlaşdırma alqoritmasıdır. Verilən bir mətn, müəyyən ölçüdə və N fərqli simvoldan ibarət olduqda, alqoritm hər fərqli simvol üçün bir kod olmaqla N kod seçir. Mətn bu kodlar vasitəsilə sıxışdırılır. Kodları seçmək üçün alqoritm N yarpağı olan ikili köklü ağac qurur. N ≥ 2 üçün ağac aşağıdakı kimi qurula bilər:
Mətndəki hər fərqli simvol üçün yalnız bir düyün olan bir ağac qurun və ona mətndəki simvolun təkrarlanma sayına uyğun bir çəki təyin edin.
Yuxarıdakı N ağacı ehtiva edən bir s dəsti qurun.
s bir ağacdan çox ağac ehtiva etdiyi müddətcə:
(a) Minimum çəkiyə malik olan t_1 ağacını seçin və onu s-dən çıxarın.
(b) Minimum çəkiyə malik olan t_2 ağacını seçin və onu s-dən çıxarın.
(c) t_1 ağacını sol alt ağac və t_2 ağacını sağ alt ağac olaraq istifadə edərək yeni bir t ağacı qurun və t_1 və t_2 ağaclarının çəkilərinin cəmini t-yə təyin edin.
(d) t ağacını s-ə daxil edin.
s-də qalan yeganə ağacı qaytarın.
"abracadabra" mətni üçün yuxarıdakı prosedurla yaradılan ağac, hər bir daxili düyünün həmin düyünə köklənmiş alt ağacın çəkisi ilə etiketləndiyi aşağıdakı şəkildəki sol tərəfdəki kimi görünə bilər. Qeyd edək ki, əldə edilən ağac, digər variantlar arasında, şəkildəki sağ tərəfdəki kimi də görünə bilər, çünki 3(a) və 3(b) addımlarında s dəsti minimum çəkiyə malik bir neçə ağac ehtiva edə bilər.
Hər fərqli simvol üçün kod, son ağacda kökdən simvola uyğun yarpağa olan yol ilə müəyyən edilir. Kodun uzunluğu həmin yoldakı kənarların sayıdır (bu, yoldakı daxili düyünlərin sayına bərabərdir). Alqoritm tərəfindən sol tərəfdəki ağac qurulduğunu fərz etsək, "r" üçün kodun uzunluğu 3, "d" üçün isə 4 uzunluğundadır.
Sizin vəzifəniz, alqoritm tərəfindən seçilən N kodun uzunluqları verildikdə, yaradılan kodların həmin N uzunluqlara malik olması üçün mətnin minimum ölçüsünü (ümumi simvol sayı) tapmaqdır.
Giriş verilənləri
Birinci sətir mətndə görünən fərqli simvolların sayını göstərən N (2 ≤ N ≤ 50) tam ədədini ehtiva edir. İkinci sətir, fərqli simvollar üçün Huffman alqoritmi ilə seçilən kodların uzunluqlarını göstərən N tam ədədi L_i ehtiva edir (1 ≤ L_i ≤ 50 üçün i = 1, 2, ..., N). Verilən uzunluqlara malik kodlar yaradan ən azı bir ağacın mövcud olduğunu fərz edə bilərsiniz.
Çıxış verilənləri
Verilən uzunluqlara malik kodlar yaradan mətnin minimum ölçüsünü (ümumi simvol sayı) göstərən bir tam ədəd ilə bir sətir çıxarın.