Page 12 - MATINF Nr. 11-12

12 D.A. Popescu, C. B˘alc˘au, D. Constantin

a
Pentru c˘ va trebui sa excludem locurile de parcare alocate rezident , ilor, vom marca ˆın v aceste
locuri astfel: v[L[i]] =true, i = 1, 2, . . . , p.

Pentru num˘ararea locurilor de parcare VIP proced˘am la fel ca la cerint , a 1 (varianta 2),
s[i] = num˘arul locurilor de parcare VIP nealocate rezident , ilor pe segmental de locuri [1, i],
i = 1, 2, . . . , n. Num˘arul cerut ˆın cerint , a 2 va fi max{s[b[i]] − s[a[i] − 1] | i = 1, 2, . . . , m}.

Problema 2 – tablou
Se d˘a un s , ir cu n numere naturale: x 1 , x 2 , . . . , x n . Cu acest s , ir se construies , te un tablou
bidimensional p˘atratic, notat cu a, de dimensiune n, astfel:

• prima linie este format˘ din s , irul dat: x 1 , x 2 , . . . , x n .
a
• ˆıncepˆand cu a doua linie, fiecare linie se construies , te folosind suma cifrelor numerelor de
pe linia anterioar˘a, astfel al j-lea termen de pe lina i este egal cu suma cifrelor celui de-al
j-lea termen de pe linia i − 1, 2 ≤ i ≤ n.

Pentru subtablouri cu laturile paralele cu marginile tabloului a, date prin linia s , i coloana
primului element, respectiv linia s , i coloana ultimului element, se dores , te suma elementelor.
Cerint , e
Cunoscˆand n, numerele x 1 , x 2 , . . . , x n s , i coordonatele colt , urilor stˆanga sus (i1, j1) s , i dreapta
jos (i2, j2) pentru un subtablou definit ca mai sus, se cere:

1. suma elementelor de pe linia 2;
2. suma elementelor subtabloului definit de colt , urile de coordonate (i1, j1) s , i (i2, j2).

Date de intrare
Pe prima linie a fis , ierului de intrare tablou.in se afl˘a C – cu valorile 1 sau 2, pe a doua
linie n, pe linia a treia s , irul de numere x 1 , x 2 , . . . , x n separate prin cˆate un spat , iu, iar pe a patra
linie numerele i1, j1, i2, j2 separate prin cˆate un spat , iu.

Date de ies , ire
a
a
Dac˘ C este 1, fis , ierul de ies , ire tablou.out va cont , ine suma de la cerint , a 1. Dac˘ C este 2,
fis , ierul de ies , ire tablou.out va cont , ine suma de la cerint , a 2.
Restrict , ii s , i preciz˘ari
1. 2 ≤ n ≤ 10000;
2. 1 ≤ x i ≤ 2000000000, i = 1, 2, . . . , n.
3. Pentru rezolvarea corect˘a a cerint , ei 1 se vor acorda 20 de puncte.
4. Pentru rezolvarea corect˘a a cerint , ei 2 se vor acorda 80 de puncte.

Exemplu

tablou.in tablou.out
1 46
3
89 3691 37
2 1 3 3
2 65
3
89 3691 37
2 1 3 3