== include(page="template/taskheader" task_id="telegraf") ==
==Include(page="template/taskheader" task_id="telegraf")==
Poveste ...
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$}):
h2. Cerinta
|_. Exemplul 1|_. Exemplul 2|_. Exemplul 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$.
h2. Restrictii
h2. 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.
h2. 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.
h2. Date de iesire
...
Fisierul $telegraf.out$ va contine un singur numar, si anume lungimea minima (in secunde) necesara pentru transmiterea textului.
h2. 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
h2. Exemplu
| telegraf.in | telegraf.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. telegraf.in|_. telegraf.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 0|11|
_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.
== include(page="template/taskfooter" task_id="telegraf") ==
==Include(page="template/taskfooter" task_id="telegraf")==
