Concursul "Urmasii lui Moisil" 2002 Clasa a IX-a |
Problema 2- T9
T9 este un sistem dezvoltat pentru a satisface nevoia de a trimite cât
mai rapid mesaje text (SMS) utilizând telefoane mobile. Un mesaj text
consta dintr-o succesiune de cuvinte separate prin câte un spatiu.
Sistemul T9 este bazat pe un dictionar stocat în memoria telefonului.
Daca utilizam acest sistem, atunci când tastam un cuvânt este suficient
sa apasam pentru fiecare litera o singura data o tasta. La actionarea unei taste
este afisat primul cuvânt din dictionar care contine, pe pozitia respectiva,
una din literele înscrise pe tasta actionata.
Cuvântul (daca exista în dictionar) va fi format luând literele
de pe pozitiile corespunzatoare din fiecare cuvânt afisat, în ordine.
Exemplu (vezi exemplul 2) secventa de taste 2 9 4 duce la aparitia cuvintelor
2 AZI adica una din literele ABC pe prima pozitie
9 AZI adica una din literele WXZY pe pozitia a doua
4 AZI adica una din literele GHI pe pozitia a treia
deci cuvântul format va fi AZI.
Fiecare litera a unui cuvânt care nu este în dictionar va fi înlocuita
cu un caracter *. Daca exista mai multe cuvinte care corespund unei anumite
secvente de actionari de taste, va fi afisat primul.
Se vor verifica toate posibilitatile de formare a unui cuvânt conform
regulilor de mai sus.
Aranjarea literelor pe tastatura telefonului mobil este urmatoarea:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Spatiu | ABC | DEF | GHI | JKL | MNO | PQRS | TUV | WXYZ |
Cerinta
Scrieti un program care sa simuleze sistemul T9 pe baza unui dictionar dat.
M - numarul de cuvinte din dictionar C1 - C1, C2, , CM reprezinta cuvintele din dictionar C2 CM N - numarul de taste actionate T1 T2 TN - cifrele înscrise pe cele N taste actionate
Date de iesire
Fisierul de iesire T9.OUT contine pe o singura linie mesajul generat de sistemul
T9 în urma apasarii celor N taste.
Restrictii
- 1 <= M <=100;
- Cuvintele C1, C2,
, CM sunt ordonate alfabetic si sunt scrise cu majuscule;
- Lungimea oricarui cuvânt este de maxim 100 de litere.
- 1 <=N <=100
- Ti in {1, 2,
, 9}, pentru orice i din {1, 2,
, N}
Exemple
T9.IN | T9.OUT |
3 ABC BBB DEF 10 2 2 2 1 2 3 1 2 2 2 |
ABC ** ABC |
T9.IN | T9.OUT |
4 AZI ESTE IERI VINERI 11 2 9 4 1 4 3 7 4 1 7 4 |
AZI IERI ** |
Timp maxim de executie: 1 secunda/test