Page 121 - MATINF Nr.2

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 121

Restrict , ii s , i preciz˘ari

• 1 ≤ m, n ≤ 200
• Componentele tabloului a sunt numere naturale ≤ 10000
• Pot exista mai multe solut , ii, dar ˆın fis , ierul de ies , ire se va scrie una dintre ele
• 30% din teste au componentele tabloului a mai mici sau cel mult egale cu 100 s , i m, n ≤ 100
• 60% din teste au componentele tabloului a mai mici sau cel mult egale cu 1000
Exemplu

operatii.in operatii.out Explicat , ie
2 3 2 a este: 1 2 4
1 2 4 1 1 0 5 5 9
2
5 5 9 2 2 3 b 1 este: 1 1 0 iar b este: 1 1 0
1
0 1 2 2 2 3 4 4 9
2
1 1 0 b 2 este: 0 1 2 iar b este: 0 1 4
2
1 1 0 1 1 0
2
2
Se observ˘a c˘a b + b = a.
2
1
Timp maxim de execut , ie: 1 secund˘a/test.
Memorie total˘a disponibil˘a 16 MB.
Doru Anastasiu Popescu, Pites , ti (Lot juniori 2009)
I 22 (varf). Se d˘a o secvent , ˘a de maxim 1000 de caractere (numai litere mici ale alfabetului
englez). Prin vˆarf se ˆınt , elege o succesiune de caractere x 1 x 2 . . . x 2k−1 cu proprietatea x 1 <
x 2 < · · · < x k > x k+1 > . . . x 2k > x 2k−1 , relat , ia de ordine fiind cea alfabetic˘a, iar num˘arul k
reprezint˘a ˆın˘alt , imea vˆarfului.
Cerint , ˘a

Se cere s˘a se determine ˆın˘at , imea celui mai ˆınalt vˆarf din secvent , a de caractere.
Date de intrare

ˆ
In fis , ierul varf.in se d˘a, pe o singur˘a linie, secvent , a de caractere.
Date de ies , ire
Fis , ierul varf.out va cont , ine ˆın˘alt , imea celui mai ˆınalt vˆarf.

Restrict , ii s , i preciz˘ari

• Secvent , a din fis , ier are maxim 1000 de caractere s , i cel put , in un caracter

Exemplu

varf.in varf.out Explicat , ie
In˘alt , imea maxim˘a este 4, pentru c˘a
abcdbabefdcbax 4 ˆ
succesiunea de caractere abefdcb este un vˆarf.
Alt vˆarf mai ˆınalt nu exist˘a.

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

Memorie total˘a disponibil˘a 2 MB.
Doru Constantin, Pites , ti