Page 120 - MATINF Nr. 3

˘
120 PROBLEME DE INFORMATICA PENTRU CONCURSURI

ˆ
I 40 (cifru). In anul 1119 a fost creat Ordinul Templului, format din templieri. Templierii
erau preg˘atit , i pentru a asigura securitatea deplas˘arii cres , tinilor ˆın timpul cruciadelor. Dup˘a o
b˘at˘alie grea aces , tia reus , esc s˘a cucereasc˘a un castel, care cont , ine un cuf˘ar cu documente foarte
importante. Cuf˘arul poate fi deschis doar dac˘a se cunoas , te un cifru, ce poate fi determinat doar
dac˘a sunt prelucrate textele ce sunt scrise pe holurile castelului. Castelul are N holuri s , i pe
fiecare dintre acestea sunt scrise texte pe un rˆand formate din M caractere litere mari, mici s , i
cifre. Caracterele de pe peret , ii holurilor se ˆımpart astfel ˆın trei categorii: litere mici, litere mari,
cifre. Pentru a g˘asi cifrul, la fiecare hol se determin˘a lungimea cea mai mare a unei secvent , e de
caractere din aceeas , i categorie cu cea a ultimului caracter. Suma acestor lungimi pentru toate
cele N holuri reprezint˘a cifrul ce deschide cuf˘arul.
Cerint , ˘a

Cunoscˆand N - num˘arul de holuri, M - num˘arul de caractere de pe fiecare hol s , i caracterele
de pe fiecare hol, trebuie s˘a determinat , i cifrul pentru deschiderea cuf˘arului.

Date de intrare
ˆ
In fis , ierul cifru.in se afl˘a pe prima linie N s , i M, numere naturale separate prin cˆate un
spat , iu s , i pe urm˘atoarele N linii cˆate M caractere (f˘ar˘a spat , ii ˆıntre ele) reprezentˆand caracterele
de pe fiecare hol (o linie pentru cˆate un hol).

Date de ies , ire
Fis , irerul cifru.out cont , ine pe prima linie cifrul.

Restrict , ii s , i preciz˘ari

• 2 ≤ N, M ≤ 5000
• Pentru 50% din teste 2 ≤ N, M ≤ 200
• Caracterele de pe hol sunt litere mari, mici sau cifre
• Prin secvent , ˘a ˆınt , elegem caractere aflate pe pozit , ii consecutive

Exemplu

cifru.in cifru.out Explicat , ie
6 7 19 Holul 1: 3 este din categoria cifre. Secvent , a cea mai lung˘a
Ab78Ha3 din categoria cifre este 78. Lungimea ei este 2.
aba5A7d Holul 2: d este din categoria litere mici. Secvent , a cea mai
aYaBA7D lung˘a din categoria litere mici este aba. Lungimea ei este 3.
aaaBBBE Holul 3: D este din categoria litere mari. Secvent , a cea mai
5555555 lung˘a din categoria litere mari este BA. Lungimea ei este 2.
QWEF4Ea Holul 4: E este din categoria litere mari. Secvent , a cea mai
lung˘a din categoria litere mari este BBBE. Lungimea ei este 4.
Holul 5: 5 este din categoria cifre. Secvent , a cea mai
lung˘a din categoria cifre este 5555555. Lungimea ei este 7.
Holul 6: a este din categoria litere mici. Secvent , a cea mai
lung˘a din categoria litere mici este a. Lungimea ei este 1.
Cifrul este 2+3+2+4+7+1 = 19.

Timp maxim de execut , ie: 0.1 sec./test. Memorie total˘a disponibil˘a 2 MB.

Doru Anastasiu Popescu, Pites , ti (Micul Gates, 2019)