Problema B: Morse modificat
Faza finala ACM, San Jose, California, 1 martie 1997
Dificultate: D1
Samuel F.B. Morse este foarte cunoscut pentru schema de codificare care
ii poarta numele. Codul Morse este foarte simplu. Fiecare litera (mare sau
mica)
este translatata intr-o secventa predefinita de linii si puncte (notate -
respectiv .). Fiecare astfel de element este transmis printr-un semnal care are
o anumita durata. Un punct este un semnal scurt, iar o linie - un semnal de
trei
ori mai lung ca durata. Intre elemente apare un scurt moment de pauza, intre
litere pauza este ceva mai lunga, iar intre cuvinte marimea este crescuta.
Aceasta dependenta intre spatiu si timp are drept efect faptul ca uneori
operatorii Morse nu transmit in mod perfect codurile, ceea ce creaza
dificultati
la receptie; mesajul este insa decodificat corect pe baza contextului.
In aceasta problema vom considera receptia cuvintelor in semnale Morse,
fara spatii intre litere. In aceasta situatie, este posibil sa se codifice
identic mesaje diferite. De exemplu, mesajul "..." poate fi
interpretat
"EEE","EI","IE","S" (folosind tabelul de codficare dat in exemplu).
Selectia
interpretarii corecte se face pe baza contextului si a supozitiei ca orice
cuvant primit apare intr-un dictionar.
In aceasta problema programul va citi o tabela cu codificarea literelor si
cifrelor in semnale Morse, o lista a cuvintelor posibile (context) si o
secventa
de cuvinte codifcate in Morse (morse). Aceste cuvinte pot fi gresite. Pentru
fiecare cuvant morse, programul trebuie sa determine - daca exista - cuvantul
corespunzator din context. Daca in context sunt mai multe cuvinte care se
potrivesc cu morse, sau daca nici un cuvant nu se potriveste perfect, programul
va scrie cuvantul care se potriveste cel mai bine si un indicator de
modificare.
Daca un cuvant unic din context se potriveste perfect cu morse, el va fi
scris pe o singura linie. Daca mai multe cuvinte din context se potrivesc
perfect cu morse se selecteaza cuvantul cu cele mai putine caractere; daca
ambiguitatea persista, oricare din cuvinte poate fi scris ca cel corect. Daca
sunt posibile mai multe solutii, cuvantul ales ca rezultat este scris cu un
semn
de exclamare dupa el.
Se considera un singur caz de eroare in transmisie, cand elementele pot fi
sau trunchiate sau adaugate la sfarsitul unui cuvant morse. Cand nu se gaseste
o
potrivire perfecta pentru morse, se scrie cuvantul din context care se
potriveste
cu cel mai lung prefix al lui morse sau are cele mai putine extra-elemente dupa
acelea din morse. Daca in aceasta situatie sunt mai multe cuvinte din context,
oricare din ele poate fi scris ca solutie. Cuvintele care nu coicid perfect
sunt
scrise cu semnul intrebarii dupa ele.
Datele de intrare vor trata numai cazuri de aceste tipuri.
Intrare:
Tabela codurilor Morse apare prima si consta din linii; fiecare linie
contine o litera mare sau o cifra C, zero sau mai multe spatii, si o secventa
de
maxim sase linii si puncte care dau codul Morse pentru C. O linie care contine
un asterisc, posibil precedat sau urmat de spatii, incheie tabela codurilor
Morse. Se presupune ca tabela contine codul Morse pentru orice caracter care
apare in sectiunea context.
Urmatoarea sectiune este context, cu cate un cuvant per linie, posibil
precedat sau urmat de blancuri. Fiecare cuvant din context are maxim zece
caractere; singurele caractere permise sunt literele mari si cifrele. Sunt
maxim
100 cuvinte in context. Sfarsitul tabelei este marcat de o linie cu un
asterisc,
posibil precedat sau urmat de blancuri.
Restul fisierului de intrare contine cuvintele morse separate prin spatii
sau caractere end-of-line. Sfarsitul fisierului este marcat de o linie cu un
asterisc, posibil precedat sau urmat de blancuri. Nici un cuvant morse nu are
mai mult de 80 caractere.
Iesire:
Pentru fiecare cuvant de intrare morse se scrie cel mai potrivit cuvant din
context, urmat eventual de ! sau ?. Fiecare cuvant se scrie pe o linie, de pe
prima coloana.
Exemplu:
Intrare: Iesire:
A .- WHAT
B -... HATH
C -.-. GOD
D -.. WROTH?
E . WHAT
F ..-. AN
G --. EARTHQUAKE
H .... IM!
I .. READY
J .--- TO
K -.- IM!
L .-..
M --
N -.
O ---
P .--.
Q --.-
R .-.
S ...
T -
U ..-
V ...-
W .--
X -..-
Y -.--
Z --..
0 ------
1 .-----
2 ..---
3 ...--
4 ....-
5 .....
6 -....
7 --...
8 ---..
9 ----.
*
AN
EARTHQUAKE
EAT
GOD
HATH
IM
READY
TO
WHAT
WROTH
*
.--.....-- .....--....
--.----.. .--.-.----..
.--.....-- .--.
..-.-.-....--.-..-.--.-.
..-- .-...--..-.--
---- ..--
*
prof. Adrian Atanasiu
Universitatea Bucuresti