Programatoarea Petra a început un curs de criptografie. Fiind un spirit creativ, Petra a creat deja o metodă elaborată de criptare a unei parole sub forma unei perechi (tabel de litere aparţinând mulţimii {‘a’...’z’}
, dicţionar de cuvinte). Din păcate pentru Petra, metoda ei de criptare a parolei, poate fi decriptată de oricine astfel:
- se iau tabelul de litere şi dicţionarul de cuvinte permise
- se listează, sortează şi numără toate cuvintele care se găsesc în tabel. Un cuvânt \(c_1c_2…c_k\) care există în dicţionar există şi în tabel dacă fiecare literă \(c_i\) apare în tabel şi pentru
i>1
, \(c_i\) este vecină în tabel cu litera \(c_{i-1}\). - din lista sortata de
T
perechi (\(cuvânt_i\), \(a_i\)), unde \(cuvânt_i\) este un cuvânt iar \(a_i\) este numărul de apariţii în tabel, reconstituie litera \(p_i\) a parolei astfel: \(p_i =\)‘a’ + (
\(a_i\)mod 26)
. Încercând să îmbunătăţească algoritmul, Petra a decis să înlocuiască unele litere din tabel cu semnul întrebării'?'
. Un semn'?'
poate fi înlocuit cu orice literă când se parcurge tabelul. Convinge-o pe Petra că, în ciuda îmbunătăţirii, îi poţi găsi parola pornind de la orice pereche de (dicţionar, tabel de litere) dată.
Cerința
Dat fiind un tabel de litere de dimensiuni N x M
, şi o listă a cuvintelor din dicţionar, să se afişeze lista sortată de T
perechi de forma 'ci: ai'
şi parola Petrei.
Date de intrare
Fişierul cuvinteascunse.in
va conţine N + C + 1
linii. Pe prima linie N, M, C
– dimensiunile tabelului, şi numărul de cuvinte din dicţionar. Apoi cele N
linii ale tabelului:
t
1,1
...t
1,m
t
2,1
...t
2,m
. . .
t
n,1
...t
n,m
urmate de cele C
cuvinte din dicţionar, fiecare pe o linie:
cuvânt
1
cuvânt
2
. . .
cuvânt
C
Date de ieșire
Fişierul cuvinteascunse.out
va conţine pe prima linie T
, numărul de cuvinte distincte găsite în tabel. Pe următoarele T
linii se vor afla perechi cuvânti ai separate printr-un spaţiu. Pe ultima linie se va afla un şir de caractere reprezentand parola Petrei.
Restricții și precizări
O secvenţă de litere reprezintă un cuvânt dacă se află în dicţionarul dat ca date de intrare. Dicţionarul conţine cuvinte formate din litere aparţinând mulţimii {‘a’...’z’}U{‘A’...’Z’}
. Literele mici şi cele mari se consideră egale. Două litere sunt vecine în tabel, dacă celulele lor au o latura sau un colţ comun. Aceeaşi litera din tabel se poate folosi de mai multe ori într-un cuvânt. Dacă acelaşi semn '?'
este folosit de mai multe ori într-un cuvânt, trebuie să reprezinte aceeaşi literă de fiecare dată.
0 < N < 6
0 < M < 6
0 < C < 20000
Exemplu:
cuvinteascunse.in
2 2 3 e a l ? ea elena arc
cuvinteascunse.out
2 ea 3 elena 1 db
Explicație
Am gasit cuvântul “ea”
de 3
ori: o data pe prima linie a tabelului, o data pe diagonala principală, inlocuind '?'
cu 'a'
, şi o data ca “?a"
inlocuind '?'
cu 'e'
. Am gasit cuvântul “elena”
o data, inlocuind '?'
cu 'n'
.