Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | huffman.in, huffman.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Coduri 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 Bi nu este prefixul unui alt cod Bj (i ≠ j).
Cerinţă
Ştiindu-se că într-un text T caracterul Ai apare de Vi ori, să se determine un şir B astfel încât înlocuind în textul T fiecare caracter Ai cu codul Bi să se obţină un text T' de lungime minimă L.
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.
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.
Restricţii
- 1 ≤ N ≤ 1 000 000.
- 1 ≤ Vk ≤ 100 000 000.
- 1 ≤ L ≤ 1018.
- Bi ≤ 1018, 1 ≤ i ≤ N.
- Soluţia nu este unică; poate fi afişată orice soluţie ce duce la o lungime L minimă.
Exemplu
| huffman.in | huffman.out |
|---|---|
| 7 1 2 2 5 5 9 10 | 86 4 2 4 3 3 0 3 6 3 7 2 1 2 2 |
Explicaţie
Caracterelor le-au fost atribuite codurile astfel:
| Numar de apariţii | Lungime | Cod binar | Lungime totală |
|---|---|---|---|
| 1 | 4 | 0010 | 4 |
| 2 | 4 | 0011 | 8 |
| 2 | 3 | 000 | 6 |
| 5 | 3 | 110 | 15 |
| 5 | 3 | 111 | 15 |
| 9 | 2 | 01 | 18 |
| 10 | 2 | 10 | 20 |
Lungimea totală a textului T' este 86.
