== include(page="template/taskheader" task_id="elicop") ==
p<>. Considerăm o matrice cu $L$ linii (numerotate de sus în jos de la $1$ la $L$) şi $C$ coloane (numerotate de la stânga la dreapta de la $1$ la $C$) care memorează doar valori $0$ şi $1$. Mai mult, valorile egale cu $1$ sunt grupate în mai multe dreptunghiuri pline, care nu se învecinează nici pe linii, nici pe coloane, nici pe diagonale. În exemplul din $fig. 1$ matricea este corectă deoarece cele $4$ dreptunghiuri de $1$ nu se învecinează. În schimb în $fig. 2$ există $2$ dreptunghiuri de $1$ învecinate pe coloană şi două învecinate pe diagonală, deci matricea este incorectă.
p<>. Un teren de fotbal este folosit pentru aterizarea elicopterelor. Gazonul de pe stadion este parcelat în pătrăţele de aceeaşi dimensiune, cu laturile paralele cu marginile terenului. Liniile cu pătrăţele de gazon sunt numerotate de sus în jos cu numerele $1, 2, ..., m$, iar coloanele cu pătrăţele de gazon sunt numerotate de la stânga la dreapta cu numerele $1, 2, ..., n$. Din cauza tipului diferit de iarbă se ştie care dintre pătrăţele de gazon sunt afectate sau nu de umbră. Acest lucru este precizat printr-un tablou bidimensional $a$ cu $m$ linii şi $n$ coloane, cu elemente $0$ şi $1$ $(a$~$ij$~ $= 0$ înseamnă că pătrăţelul aflat pe linia $i$ şi coloana $j$ este afectat de umbră, iar $a$~$ij$~ $= 1$ înseamnă că pătrăţelul aflat pe linia $i$ şi coloana $j$ nu este afectat de umbră). Fiecare elicopter are $3$ roţi pe care se sprijină. Roţile fiecărui elicopter determină un triunghi dreptunghic isoscel. Elicopterele aterizează, astfel încât triunghiurile formate să fie cu catetele paralele cu marginile terenului. În exemplul următor avem patru elicoptere.
!problema/elicop?x.jpg!
p<>. În această matrice se pot face deplasări doar pe direcţiile Vest şi Nord în elemente egale cu $0$, deci din poziţia $(i, j)$ se poate ajunge doar într-una dintre poziţiile $(i, j-1)$ şi $(i-1, j)$, marcate cu $0$. În acest fel, pornind de la o anumită poziţie, prin deplasări succesive, pot fi accesate un anumit număr de elemente ale matricei egale cu $0$. De exemplu, în $fig. 1$, din poziţia $(2, 4)$ pot fi accesate $5$ componente egale cu $0$, iar din poziţia $(5, 4)$ pot fi accesate $14$ componente egale cu $0$.
Trebuie să răspundeţi la $Q$ întrebări, fiecare întrebare fiind de forma: “Câte din elementele egale cu zero ale matricei pot fi accesate din poziţia $(i, j)$?”
p<>. Pentru a preciza poziţia unui elicopter pe teren este suficient să cunoaştem linia şi coloana vărfurilor ipotenuzei şi poziţia vârfului deasupra (codificată prin $1$) sau dedesubtul ipotenuzei (codificată prin $-1$). Pentru exemplu, elicopterul din stânga sus este dat prin $(1, 1), (3, 3)$ şi $-1$, cel din dreapta sus prin $(1, 9), (5, 5)$ şi $1$, cel din stânga jos prin $(5, 1), (6, 2)$ şi $1$, iar cel din dreapta jos prin $(5, 9), (6, 8)$ şi $1$.
Un elicopter se consideră că a aterizat greşit, dacă triunghiul format sub el (definit mai sus) are mai mult de jumătate din pătrăţele afectate de umbră.
Administratorul terenului de fotbal doreşte să determine numărul $N1$ de elicoptere, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat greşit în ordine crescătoare: $e1, e2, ..., eN2$, ştiind că există $k$ elicoptere codificate prin numerele $1, 2, ..., k$.
h2. Cerinţă
