Se citesc n simboluri si frecventele lor de aparitie. Construiti, folosind metoda Greedy (algoritmul lui Huffman: combinati mereu cele doua frecvente minime disponibile intr-un nod nou, cu frecventa egala cu suma lor, pana ramane un singur nod), un cod Huffman optim si determinati costul total al codificarii (suma tuturor sumelor obtinute la fiecare combinare, echivalenta cu lungimea totala, in biti, a mesajului codificat).
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n frecvente.
- Date de iesire
- Se afiseaza un singur numar: costul total minim al codificarii. Daca n=1, costul este 0.
- Restrictii
- 1 <= n <= 100000, 1 <= frecventa <= 10^9
Exemple
Exemplul 1
Intrare
4 5 9 12 13
Iesire
78
Exemplul 2
Intrare
5 5 9 12 13 16
Iesire
124