Page 166 - MATINF Nr. 1

˘
166 PROBLEME DE INFORMATICA PENTRU CONCURSURI

Exemple

cuvinte.in cuvinte.out Explicat , ie
1 126 p = 1
ababcd POZ poate fi 126 sau 346, iar
abd 126 este cel mai mic. Pen-
tru POZ=126, ˆınseamn˘a c˘a se
p˘astreaz˘a din c 1 literele de pe
pozit , iile 1, 2, 6, se s , terg cele de
pe pozit , iile 3, 4, 5 s , i se obt , ine c 2 .

cuvinte.in cuvinte.out Explicat , ie

2 29 p = 2
adcd Cuvintele ce se pot forma cu res-
ad pectarea regulilor din enunt , sunt:
a, d, c,
ad, da, ac, ca, dc, cd, aa, dd,
dac, dca, adc, acd, cda, cad,
daa, ada, aad, caa, aca, aac,
cdd, dcd, ddc, add, dad, dda.

Timp maxim de execut , ie: 1 secund˘a/test.

Memorie total˘a disponibil˘a 4 MB, din care 2 MB pentru stiv˘a.

Doru Anastasiu Popescu, Pites , ti (Info-Oltenia, 2016)
ˆ
I 13 (litere). In fiecare p˘atr˘at , el al unei table de s , ah de dimensiune m × n se afl˘a cˆate o pies˘a
pe care este scris˘a o liter˘a mic˘a din alfabetul englez. Georgic˘a dores , te s˘a-s , i verifice cunos , tint , ele
de informatic˘a folosind tabla de s , ah s , i piesele. Astfel el dores , te s˘a determine:

1. num˘arul de cuvinte Nr de lungime k ce se pot forma, cu litere distincte s , i ˆın ordine
alfabetic˘a, folosind piese de pe tabla de s , ah;
2. lungimea minim˘a L a unui cuvˆant format cu piese vecine de pe tabla de s , ah ce cont , in
numai vocale, astfel ˆıncˆat s˘a cont , in˘a o pies˘a de pe prima linie s , i o pies˘a de pe ultima linie;
dou˘a piese sunt vecine, dac˘a au o latur˘a comun˘a.

Cerint , ˘a

Cunoscˆand numerele m, n, k s , i piesele de pe tabla de s , ah se cere:
1. num˘arul Nr cu semnificat , ia de mai sus;

2. num˘arul L cu semnificat , ia de mai sus.

Date de intrare
Fis , ierul de intrare litere.in cont , ine pe prima linie un num˘ar natural p. Pentru toate testele
de intrare, num˘arul p poate avea doar valoarea 1 sau 2.

Pe linia a doua se afl˘a m, n s , i k, separate prin cˆate un spat , iu, iar pe urm˘atoarele m linii
literele tabloului, f˘ar˘a spat , iu ˆıntre ele.