== include(page="template/taskheader" task_id="huffman") ==

Poveste şi cerinţă...

Se dă un alfabet $A$ format din $N$ caractere. Numim cod binar un şir de cifre de 0 şi 1 de o lungime finită. Fie $B$ un şir de coduri binare cu proprietatea că niciun cod $B{~i~}$ nu este prefixul unui alt cod $B{~j~}$ $(i ≠ j)$.
 
h2. Cerinţă
 
Ştiindu-se că într-un text T caracterul $A{~i~}$ apare de $V{~i~}$ ori, să se determine un şir $B$ astfel încât înlocuind în textul $T$ fiecare caracter $A{~i~}$ cu codul $B{~i~}$ să se obţină un text $T'$ de lungime minimă $L$.

h2. Date de intrare

Fişierul de intrare $huffman.in$ ...

Fişierul de intrare $huffman.in$ va conţine pe prima linie numărul natural $N$. Pe următoarele $N$ linii se vor afla elementele şirului $V$, în ordine crescătoare.

h2. Date de ieşire

În fişierul de ieşire $huffman.out$ ...

În fişierul de ieşire $huffman.out$ se va afişa pe prima linie lungimea minima $L$ a textului $T'$. Pe următoarele $N$ linii se vor afişa elementele şirului $B$, fiecare cod fiind scris în baza $10$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 5 000 000.$
* $1 ≤ V{~k~} ≤ 100 000 000.$
* $1 ≤ L ≤ 10^18^.$
* $B{~i~} ≤ 10^18^, 1 ≤ i ≤ N.$

h2. Exemplu

h3. Explicaţie

...

== include(page="template/taskfooter" task_id="huffman") ==