Page 122 - MATINF Nr.2

˘
122 PROBLEME DE INFORMATICA PENTRU CONCURSURI

I 23 (char). Alex a primit de la Mos , Cr˘aciun un joc foarte interesant. Jocul este format dintr-o
secvent , ˘a de n litere mici. Fiecare liter˘a are o anumit˘a putere, dat˘a printr-un num˘ar natural.
Puterea k a unei litere c const˘a ˆın faptul c˘a, dac˘a aceasta este atins˘a, toate literele din secvent , ele
de cˆate k litere din stˆanga s , i din dreapta sa se transform˘a ˆın c. Spre exemplu, dac˘a litera n are
puterea 2, atunci dup˘a atingere secvent , a abcbnpbrr se transform˘a ˆın abnnnnnrr. Cunoscˆand
puterea fiec˘arei litere, jocul const˘a ˆın determinarea num˘arului maxim m de litere care dup˘a
atingere s˘a transforme orice liter˘a din secvent , ˘a cel mult o dat˘a.

Cerint , ˘a
S˘a se scrie un program care s˘a citeasc˘a o secvent , ˘a cu n litere, puterea fiec˘arei litere din
secvent , ˘a s , i s˘a afis , eze num˘arul de litere cu puterea maxim˘a s , i num˘arul m.

Date de intrare
ˆ
In fis , ierul char.in se dau:
- pe prima linie num˘arul n;

- pe a doua linie n litere, f˘ar˘a spat , iu ˆıntre ele;
- pe a treia linie num˘arul h de litere distincte din secvent , ˘a;

- pe a patra linie h numere naturale, separate ˆıntre ele prin cˆate un spat , iu, reprezentˆand
puterea literelor din secvent , ˘a, ˆın ordine alfabetic˘a.
Date de ies , ire

Fis , ierul char.out va cont , ine pe prima linie num˘arul de litere cu puterea maxim˘a, iar pe
linia a doua num˘arul m.

Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 10000

• 1 ≤ putere liter˘a ≤ 100
• Dac˘a ˆın stˆanga sau ˆın dreapta unei litere sunt mai put , ine litere decˆat puterea, atunci
atingerea conduce la transformarea tuturor literelor din stˆanga, respectiv din dreapta

• Se acord˘a 30% din punctaj pentru determinarea num˘arului de litere cu puterea maxim˘a s , i
70% din punctaj pentru determinarea num˘arului m

Exemplu

char.in char.out Explicat , ie
12 6 Litera a are puterea 2, litera b puterea 5, litera c puterea 3,
acbbxacbbbxb 3 respectiv litera x puterea 2.
4 Litera cu puterea maxim˘a este b, care apare de s , ase ori.
2 5 3 2 Num˘arul maxim de litere care pot fi atinse astfel ˆıncˆat
ˆın secvent , ˘a s˘a se transforme orice liter˘a cel mult o dat˘a este 3
(de exemplu se pot atinge literele de pe pozit , iile 1, 6, 11,
pozit , iile ˆıncepˆand cu indicele 1).

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

Memorie total˘a disponibil˘a 2 MB.

Doru Anastasiu Popescu, Pites , ti