1829 - Cuvinte Ascunse - Revision history

RebecaBud: /* Enunt */

2024-06-03T17:05:59Z

Enunt

← Older revision		Revision as of 17:05, 3 June 2024
Line 2:		Line 2:
	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:		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 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~~		* se listează, sortează şi numără toate cuvintele care se găsesc în tabel. Un cuvânt c1c2…ckcare există în dicţionar există şi în tabel dacă fiecare literă ci apare în tabel şi pentru i>1, cieste vecină în tabel cu litera ci−1.
	~~care~~ există în dicţionar există şi în tabel dacă fiecare literă ci		* din lista sortata de T perechi (cuvânti, ai), unde cuvântieste un cuvânt iar ai este numărul de apariţii în tabel, reconstituie litera pi a parolei astfel: pi=‘a’ + ( aimod 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ă.
	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ântieste un cuvânt iar ai este numărul de apariţii în tabel, reconstituie litera pi a parolei astfel: pi=‘a’ + ( aimod 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 ==		== Cerinţa ==

RebecaBud: /* Enunt */

2024-06-03T17:05:32Z

Enunt

← Older revision		Revision as of 17:05, 3 June 2024
Line 6:		Line 6:
	apare în tabel şi pentru i>1, ci		apare în tabel şi pentru i>1, ci
	este vecină în tabel cu litera ci−1.		este vecină în tabel cu litera ci−1.
	din lista sortata de T perechi (cuvânti, ai		din lista sortata de T perechi (cuvânti, ai), unde cuvântieste un cuvânt iar ai este numărul de apariţii în tabel, reconstituie litera pi a parolei astfel: pi=‘a’ + ( aimod 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ă.
	), 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 ==		== 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.		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.

RebecaBud: Pagină nouă: == 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 cuvin...

2024-06-03T17:04:55Z

Pagină nouă: == 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 cuvin...

New page

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

== 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>