Page 116 - MATINF Nr. 11-12

˘
116 PROBLEME DE INFORMATICA PENTRU CONCURSURI

Exemplu
sdlm.in sdlm.out Explicat , ie
6 3 2 Exist˘a dou˘a subs , iruri des-
10 3 19 8 6 15 cresc˘atoare de lungime ma-
xim˘ 3:
a
10 8 6
19 8 6

Timp maxim de execut , ie: 0.1 secund˘a/test.
a
a
Memorie total˘ disponibil˘ 2 MB.
Doru Constantin, Pites , ti
I 143 (pp). Se d˘a un tablou p˘atratic de dimensiune n cu elemente numere naturale s , i k un
num˘ar natural nenul, k ≤ n. Se cere s˘a se determine num˘arul de subtablouri p˘atratice de
dimensiune k, care au un num˘ar maxim de numere p˘atrate perfecte.

Cerint , ˘
a
Cunoscˆand n, k s , i elementele tabloului p˘atratic determinat , i num˘arul de subtablouri p˘atratice
de dimensiune k cu num˘ar maxim de p˘atrate perfecte.

Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 100.
• Numerele din tablou sunt ≤ 1000000.

Date de intrare
Fis , ierul pp.in cont , ine pe prima linie n s , i k, apoi pe liniile urm˘atoare elementele tabloului
p˘atratic separate prin cˆate un spat , iu.

Date de ies , ire

Fis , ierul de ies , ire pp.out va cont , ine pe prima linie num˘arul cerut.
Exemplu
pp.in pp.out Explicat , ii
3 2 3 Subtablourile de dimensiune 2 care cont , in un
4 11 10 num˘ar maxim de numere p˘atrate perfecte sunt:
11 100 121 ———
10 10 10 4 11
11 100
———
11 10
100 121
———
100 121
10 10
———

Timp maxim de execut , ie: 0.1 secund˘a/test.
Memorie total˘ disponibil˘ 2 MB.
a
a
Doru Anastasiu Popescu, Pites , ti