h3. (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

Se observa ca daca stim linia {$L{~1~}$} si suma asociata zonei {$1$}, coloana {$C{~1~}$} este unic determinata deoarece elementele matricii initiale erau pozitive: pornind cu submatricea de colturi {$(1, 1)$} si {$(L, 1)$}, va trebui sa crestem $C{~1~}$ pana cand suma submatricii de colturi {$(1, 1)$} si {$(L{~1~}, C{~1~})$} va deveni cat am stabilit initial. Cum suma submatricii de colturi {$(1, 1)$} si {$(L{~1~}, X)$} este mai mica decat suma submatricii de colturi {$(1, 1)$} si {$(L{~1~}, X+1)$}, cautarea coloanei {$C{~1~}$} poate fi realizata prin cautare binara. Dupa ce am determinat {$C{~1~}$}, stabilim care dintre cele 8 sume ramase este valoarea zonei {$2$} si determinam in mod similar valoarea coloanei {$C{~2~}$}. Apoi stabilim care dintre cele 7 sume ramase este valoarea pe care o vom asocia zonei {$4$} si determinam si {$L{~2~}$}. Pentru un cvadruplu astfel determinat, {$L{~1~}$}, {$C{~1~}$}, {$L{~2~}$} si {$C{~2~}$}, vom determina toate cele 9 sume care se formeaza si daca ele sunt egale cu sumele impuse initial, atunci inseamna ca avem o solutie. Dintre toate solutiile posibile o vom afisa in final pe cea care respecta conditiile de minimalitate enuntate.

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).

In momentul in care cautam binar o linie sau o coloana va trebui sa aflam suma pentru o anumita submatrice. Pentru a realiza acest lucru eficient, vom construi de la inceput matricea de sume partiale {$S$}, unde {$S{~i,j~}$} reprezinta suma elementelor din submatricea care are coltul stanga-sus in {$(1, 1)$} si coltul dreapta-jos in {$(i, j)$}. Astfel, suma submatricii de colturi {$(x{~1~}, y{~1~})-(x{~2~}, y{~2~})$} va fi egala cu {$S{~x2,y2~}$} - {$S{~x1-1,y2~}$} - {$S{~x2,y1-1~}$} + {$S{~x1-1,y1-1~}$}.
 
Problema este astfel rezolvata in intregime. Complexitatea algoritmului este {$O(N^2^)$}.

h2. Plantatie