Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-12-02 18:03:50.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:huffman.in, huffman.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

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.inhuffman.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ţiiLungimeCod binarLungime totală
1400104
2400118
230006
5311015
5311115
920118
1021020

Lungimea totală a textului T' este 86.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?