Page 11 - MATINF Nr. 3

Concursul de Informatic˘a Programming Day 11

Dou˘a elemente din tabloul bidimensional
A sunt vecine dac˘a acestea se afl˘a pe aceeas , i li-
nie s , i pe coloane consecutive sau pe aceeas , i co-
loan˘a s , i pe linii consecutive. Definim not , iunea
de lant , ca fiind o succesiune ordonat˘a de ele-
mente vecine, care nu se repet˘a (trece printr-
un element din tablou o singur˘a dat˘a). Pentru
Fig. 2: Exemple de lant , uri.
cuvˆantul C = ”VARA” s , i tabloul bidimen-
sional A al˘aturat sunt marcate 4 lant , uri ana-
grame pentru C (dintr-un total de 10 lant , uri
anagrame pentru C).

Cerint , ˘a
Cunoscˆand cuvˆantul C, dimensiunile M, N s , i elementele tabloului bidimensional A se cere:

1. num˘arul de aparit , ii ˆın tabloul A a ultimei litere din C;
2. num˘arul de lant , uri din tabloul A, care sunt anagrame ale cuvˆantului C.

Date de intrare
Fis , ierul de intrare cuvinte.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 cuvˆantul C, pe linia a treia se afl˘a M s , i N separate printr-un spat , iu,
iar pe urm˘atoarele M linii cˆate N litere mari, f˘ar˘a spat , ii ˆıntre ele, ce formeaz˘a tabloul A.

Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.

ˆ
In acest caz,ˆın fis , ierul de ies , ire cuvinte.out se va scrie un singur num˘ar natural reprezentˆand
num˘arul de aparit , ii ˆın tabloul A a ultimei litere din C.
Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.

ˆ
In acest caz,ˆın fis , ierul de ies , ire cuvinte.out se va scrie un singur num˘ar natural reprezentˆand
num˘arul de lant , uri din tabloul A, care sunt anagrame ale cuvˆantului C.

Restrict , ii s , i preciz˘ari
• C are cel mult 10 litere
• 1 ≤ M, N ≤ 41
• Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 25% din punctaj, iar pentru cerint , a 2 se
acord˘a 75% din punctaj

Exemple

cuvinte.in cuvinte.out Explicat , ie
1 6 p = 1
VARA Ultima liter˘a din cuvˆantul C (VARA) este A. A apare in
5 6 tablou de 6 ori.
VARAXV
MREYAR
EAABAX
TIGDVG
EOGERG