Fişierul intrare/ieşire:telegraf.in, telegraf.outSursăONI 2003
AutorMihai PatrascuAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Telegraf

Pana nu demult, comunicatia la distanta se facea cu ajutorul telegrafului. Folosind telegraful, se pot transmite doua tipuri de semnale: punct si linie. In general, dorim sa transmitem texte formate din litere ale alfabetului latin si cifre (in total 36 de simboluri). Trebuie deci sa folosim o codificare, adica sa asociem fiecaruia din cele 36 de simboluri o succesiune distincta de linii si puncte. Pentru a putea decodifica o succesiune receptionata de linii si puncte, este necesar ca nici un simbol sa nu aiba o codificare identica cu inceputul codificarii pentru un alt simbol. Sa consideram cateva exemple (presupunand ca nu vrem sa transmitem decat literele A, B, C):

Exemplul 1Exemplul 2Exemplul 3
A = ..A = .--A = .-..
B = .-B = .-B = -.
C = -C = -C = .-.

Exemplul 1 reprezinta o codificare corecta. Exemplul 2 reprezinta o codificare gresita, pentru ca inceputul codificarii pentru A este identic cu codificarea pentru B (deci, o secventa de genul .-- este ambigua, putand insemna si A si BC). Exemplul 3 este de asemenea o codificare gresita pentru ca inceputul codificarii pentru A este identic cu codificarea pentru C (o secventa precum .-..-. este ambigua, putand insemna fie AB, fie CC). Se stie ca intr-o transmisie telegrafica, punctul dureaza o secunda, iar linia 2 secunde. Putem calcula astfel timpul necesar transmiterii unui text. Folosind codificarea din exemplul 1, transmiterea textului CABCA = -...--.. dureaza 11 secunde. Observati ca lungimea transmisiei se poate calcula si astfel: 2(A) + 1(B) + 2(C) = 2(..) + 1(.-) + 2(-) = 2*2 + 1*3 + 2*2 = 11.

Cerinta

Se considera un text, dat prin frecventa aparitiei fiecarui simbol (dintre cele 36 considerate). Sa se gaseasca durata minima necesara transmiterii acelui text, folosind o codificare aleasa corespunzator.

Date de intrare

Fisierul telegraf.in contine o singura linie cu 36 de numere intregi nenegative, separate prin cate un spatiu, reprezentand numarul de aparitii ale fiecarui simbol in textul ce trebuie transmis.

Date de iesire

Fisierul telegraf.out va contine un singur numar, si anume lungimea minima (in secunde) necesara pentru transmiterea textului.

Restrictii si precizari

  • Nici unul din cele 36 de simboluri nu apare de mai mult de 1 000 000 de ori in textul considerat
  • Exista cel putin doua simboluri cu numar de aparitii nenul
  • 40% dintre teste vor contine maxim 16 simboluri cu frecventa de aparitie nenula

Exemplu

telegraf.intelegraf.out
2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 011

Explicatie: Se constata ca este optim sa se transmita acest text folosind codificarea din Exemplul 1, obtinand o lungime minima a transmisiei de 11 secunde.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content