Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-02-18 14:35:37.
Revizia anterioară   Revizia următoare  

Solutii Runda 2

Amlei

(problema usoara, clasa a 9-a, clasa a 10-a)

Tricouri

(problema medie, clasa a 9-a)

Zone

(problema grea, clasa a 9-a)

Pentru linia l1 si sumele corespunzatoarele zonelor 1, 2 si 4 o solutie potentiala ( adica un cvadruplu de forma l1, l2, c1, c2 ) este unic determinata deoarece elementele matricii initiale sunt pozitive. Astfel, vom determina intai coloana c1 pentru ca suma din regiunea 1 sa fie S1. Pentru c1 stabilit vom afla c2 astfel incat suma din regiunea 2 sa fie S2. Pentru a determina

Pentru a afla suma unei submatrici in O(1) se foloseste o matrice auxiliara de sume partiale: M[i][j] = suma elementelor din submatricea care are coltul stanga-sus in (1, 1) si coltul dreapta-jos in (i, j).

Plantatie

(problema medie, clasa a 10-a)

Culori

(problema grea, clasa a 10-a, problema medie, clasele 11-12)

Reguli

(problema usoara, clasele 11-12)

Ghiozdan

(problema grea, clasele 11-12)

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: