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

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 lungime $N$ de coduri binare cu proprietatea că niciun cod $B{~i~}$ nu este prefixul unui alt cod $B{~j~}$ $(i ≠ j)$.

Codurile Huffman reprezintă o tehnică foarte eficientă pentru compactarea datelor, spaţiul economisit fiind adesea cuprins între $20%$ şi $90%$. Algoritmul greedy pentru realizarea acestei codificări înregistrează frecvenţele de apariţie ale fiecărui simbol dintr-un fişier text, după care utilizează o modalitate optimă pentru reprezentarea fiecărui simbol sub forma unui şir binar.
 
Astfel, se dă un alfabet $A = {a{~1~},a{~2~},...,a{~n~}}$ format din $n$ caractere. Numim cod binar un şir de cifre de $0$ şi $1$ de o lungime finită. Fie $B$ un şir de lungime $n$ 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$.

Ş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ă $lg$.

h2. Date de intrare

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.

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$ se va afişa pe prima linie lungimea minima $L$ a textului $T'$. Pe următoarele $N$ linii se vor afişa $2$ numere naturale caracterizând elementele şirului $B$: lungimea fiecărui cod şi reprezentarea sa în baza $10$.

În fişierul de ieşire $huffman.out$ se va afişa pe prima linie lungimea minimă $lg$ a textului $T'$. Pe următoarele $n$ linii se vor afişa câte două numere naturale caracterizând elementele şirului $B$: lungimea fiecărui cod şi reprezentarea sa în baza $10$.

h2. Restricţii

* $1 ≤ N ≤ 1 000 000$.
* $1 ≤ V{~k~} ≤ 100 000 000$.
* $1 ≤ L ≤ 10^18^$.
* $B{~i~} ≤ 10^18^, 1 ≤ i ≤ N$.
* Soluţia nu este unică; poate fi afişată orice soluţie ce duce la o lungime $L$ minimă.

* $1 ≤ n ≤ 1 000 000$.
* $1 ≤ v{~i~} ≤ 100 000 000, 1 ≤ i ≤ n$.
* $1 ≤ lg ≤ 10^18^$.
* $b{~i~} ≤ 10^18^, 1 ≤ i ≤ n$.
* Soluţia nu este unică; poate fi afişată orice soluţie ce duce la o lungime $lg$ minimă.

h2. Exemplu

h3. Explicaţie

!problema/huffman/Huffman_tree_2.svg 50%!
 

Caracterelor le-au fost atribuite codurile astfel:
table(example). |_. Numar de apariţii |_. Lungime |_. Cod binar |_. Lungime totală |

| 9 | 2 | 01 | 18 |
| 10 | 2 | 10 | 20 |

Lungimea totală a textului $T'$ este 86.

Lungimea totală a textului $T'$ este $86$.

h2. Soluţie

Problema se rezolvă printr-un algoritm greedy, codarea Huffman. Se pot considera cele $N$ caractere noduri într-un graf, având fiecare un cost egal cu numărul de apariţii al caracterului în textul $T$. La fiecare pas se creeaza un nod nou şi se duc de la acesta $2$ muchii către nodurile de cost minim care nu au fost încă unite, costul acestuia fiind egal cu suma costurilor celor $2$ fii. Pentru a putea reconstitui ulterior codurile, se asociaza celor $2$ muchii valoarile $0$ şi $1$. Se va obţine un arbore binar cu $2*N-1$ noduri, suma costurilor nodurilor interne fiind egală cu lungimea textului $T'$.

Problema se rezolvă printr-un algoritm greedy, codarea Huffman. Se pot considera cele $N$ caractere noduri într-un graf, având fiecare un cost egal cu numărul de apariţii al caracterului în textul $T$. La fiecare pas se creeaza un nod nou şi se duc de la acesta $2$ muchii către nodurile de cost minim care nu au fost încă unite, costul acestuia fiind egal cu suma costurilor celor $2$ fii. Pentru a putea reconstitui ulterior codurile, se asociaza celor $2$ muchii valorile $0$ şi $1$. Se va obţine un arbore binar cu $2*N-1$ noduri, suma costurilor nodurilor interne fiind egală cu lungimea textului $T'$.

Algoritmul se poate generaliza pentru coduri in baza $K$, selectand la fiecare pas cele mai mici K noduri pentru a le uni cu nodul nou creat. De asemenea, trebuie create caractere fictive cu $0$ aparitii, pentru ca numărul iniţial de noduri să fie de forma $X * (K-1) + 1$.
h3. Etape de rezolvare

O 'soluţie':job_detail/370657?action=view-source în care căutarea celor $2$ noduri de cost minim se face liniar are o complexitate $O(N^2^)$ şi obţine $30$ de puncte. Folosind un heap pentru a extrage nodurile de cost minim, complexitatea scade la $O(N log~2~ N)$. Această 'soluţie':job_detail/370924?action=view-source obţine $70$ de puncte. În cazul în care costurile nodurilor sunt date în ordine crescătoare, se pot ţine $2$ cozi, conţinând nodurile iniţiale, respectiv nodurile interne. Observând că nodurile sunt sortate crescător după cost, se pot extrage cele $2$ minime şi introduce nodul nou în $O(1)$. Această 'soluţie':job_detail/370923?action=view-source obţine $100$ de puncte.

O 'soluţie':job_detail/370657?action=view-source în care căutarea celor $2$ noduri de cost minim se face liniar are o complexitate $O(N^2^)$ şi obţine $30$ de puncte. Folosind un heap pentru a extrage nodurile de cost minim, complexitatea scade la $O(N log{~2~} N)$. Această 'soluţie':job_detail/370924?action=view-source obţine $70$ de puncte. În cazul în care costurile nodurilor sunt date în ordine crescătoare, se pot ţine $2$ cozi, conţinând nodurile iniţiale, respectiv nodurile interne. Observând că nodurile sunt sortate crescător după cost, se pot extrage cele $2$ minime şi introduce nodul nou în $O(1)$. Această 'soluţie':job_detail/370923?action=view-source obţine $100$ de puncte.

h2. Probleme propuse