Page 11 - MATINF Nr.2

Concursul de Informatic˘a Programming Day 11

1. suma elementelor celui mai din dreapta-jos subtablou de dimensiune k;
2. num˘arul de subtablouri de dimensiune k care au suma elementelor un num˘ar prim.

Date de intrare

Fis , ierul de intrare subtablou.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 a doua linie se afl˘a dimensiunea
n a tablei s , i num˘arul k, separate printr-un spat , iu. Urmeaz˘a n linii cu cˆate n cifre separate prin
cˆate un spat , iu, ce reprezint˘a valorile de pe jetoanele aflate pe tabla jocului.

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 subtablou.out se va scrie un singur num˘ar natural reprezentˆand suma
elementelor celui mai din dreapta-jos subtablou de dimensiune k.
ˆ
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 subtablou.out se va scrie num˘arul de subtablouri de dimensiune k care au
suma elementelor un num˘ar prim.

Restrict , ii s , i preciz˘ari

1. 1 ≤ n ≤ 200
2. 1 ≤ k ≤ n
3. Pntru rezolvarea corect˘a a cerint , ei 1 se acord˘a 20% din punctaj

Exemple

subtablou.in subtablou.out Explicat , ie
1 14 p = 1
3 2 Cel mai din dreapta-jos subtablou
1 1 0 de dimensiune k = 2 este
3 0 1 0 1
3 5 8 5 8
cu suma elementelor 14.
subtablou.in subtablou.out Explicat , ie
2 3 p = 2
3 2
3 2 Sunt 3 subtablouri de dimensiune k = 2
1 1 0 care au suma elementelor un num˘ar prim.
3 0 1
3 5 8 Acestea sunt:
1 1 1 0 3 0
3 0 0 1 3 5
Suma=5 Suma=2 Suma=11

Timp maxim de execut , ie: 0.1 secunde/test.

Memorie total˘a disponibil˘a 4 MB.
Doru Anastasiu Popescu, Costel B˘alc˘au, Pites , ti, Gabriel Boroghin˘a, Bucures , ti