1829 - Cuvinte Ascunse

Enunt

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 c1c2…ck

care există în dicţionar există şi în tabel dacă fiecare literă ci
apare în tabel şi pentru i>1, ci
este vecină în tabel cu litera ci−1.

din lista sortata de T perechi (cuvânti, ai ), unde cuvânti

este un cuvânt iar ai
este numărul de apariţii în tabel, reconstituie litera pi
a parolei astfel: pi=
‘a’ + ( ai
 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: t1,1 ...t1,m t2,1 ...t2,m . . . tn,1 ...tn,m urmate de cele C cuvinte din dicţionar, fiecare pe o linie: cuvânt1 cuvânt2 . . . cuvântC

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

Exemplul 1

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'.

Rezolvare

<syntaxhighlight lang="python" line> def is_valid_cell(i, j, n, m):

   return 0 <= i < n and 0 <= j < m

def search_word(grid, word, n, m, visited, i, j, idx):

   if idx == len(word):
       return True
   if not is_valid_cell(i, j, n, m) or visited[i][j] or grid[i][j] != word[idx]:
       return False
   visited[i][j] = True
   for di in [-1, 0, 1]:
       for dj in [-1, 0, 1]:
           if (di, dj) != (0, 0) and search_word(grid, word, n, m, visited, i + di, j + dj, idx + 1):
               return True
   visited[i][j] = False
   return False

def count_word_occurrences(grid, word, n, m):

   count = 0
   for i in range(n):
       for j in range(m):
           if grid[i][j] == word[0]:
               visited = [[False] * m for _ in range(n)]
               if search_word(grid, word, n, m, visited, i, j, 0):
                   count += 1
   return count

def main():

   with open("cuvinteascunse.in", "r") as fin:
       n, m, c = map(int, fin.readline().split())
       grid = [fin.readline().split() for _ in range(n)]
       words = [fin.readline().strip() for _ in range(c)]

   word_counts = {}
   for word in words:
       count = count_word_occurrences(grid, word, n, m)
       if count > 0:
           word_counts[word] = count

   sorted_words = sorted(word_counts.items(), key=lambda x: x[1], reverse=True)

   with open("cuvinteascunse.out", "w") as fout:
       fout.write(str(len(sorted_words)) + "\n")
       for word, count in sorted_words:
           fout.write(f"{word} {count}\n")
       password = ""
       for i in range(n):
           for j in range(m):
               if grid[i][j] != "?":
                   password += chr(ord("a") + (count_word_occurrences(grid, grid[i][j], n, m) % 26))
       fout.write(password + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>