==Include(page="template/taskheader" task_id="telegraf")==
==Include(page="template/raw")==
Link: [1]File-List
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):
h2. Exemplul 1 Exemplul 2 Exemplul 3
A = .. A = .-- A = .-..
B = .- B = .- B = -.
C = - C = - C = .-.
h2. 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. 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
Ÿ 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 Explicatie
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 Se constata ca este optim sa
se transmita acest text
folosind codificarea din
h2. Exemplul 1, obtinand o lungime
minima a transmisiei de 11
secunde.
==Include(page="template/taskheader" task_id="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 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. 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
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")==
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/telegraf/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="telegraf")==
