Parcele2

parcele2

== include(page="template/taskheader" task_id="parcele2") ==
O suprafata de pamant este impartita in $NxM$ parcele de teren. Pe aceasta suprafata au fost plantati pe parcele de coordonate cunoscute un numar $P$ de copaci, fiecare intr-un anumit an calendaristic. Astfel pentru un copac se cunosc valorile $Ai$, $Xi$, $Yi$, cu 1 ≤ i ≤ $P$, unde $Ai$ este anul in care a fost plantat copacul $i$ iar $Xi$ si $Yi$ sunt coordonatele parcelei pe care a fost plantat. Se stie ca fiecare copac isi mareste inaltimea de $K$ ori in fiecare an. Astfel, in anul in care a fost plantat, copacul are inaltimea $1$, iar in al doilea an $k$, in al treilea $k^2^$ etc.

Definim o regiune ca fiind o suprafata de teren dreptunghiulara cu laturile paralele cu cele ale terenului, specificata prin parcelele stanga-sus si dreapta-jos: ( $Xs$, $Ys$ ), ( $Xd$, $Yd$ ).

Definim o regiune ca fiind o suprafata de teren dreptunghiulara cu laturile paralele cu cele ale terenului, specificata prin parcelele stanga-sus si dreapta-jos: ($Xs$, $Ys$), ($Xd$, $Yd$).

O regiune este considerata "frumoasa", daca pentru fiecare inaltime $H$ exista un numar par de copaci cu acea inaltime.
In anul $2015$ proprietarul a descoperit o metoda ingenioasa a adauga noi copaci de orice inaltime. Folosind aceasta metoda el este interesat sa "infrumuseteze" pe rand $Q$ regiuni ale suprafetei, pe parcursul acestui an. Copacii pot fi adaugati insa **doar pe parcela din dreapta jos** a regiunilor de interes si se va planta un numar minim de copaci. Dupa ce regiunea a devenit frumoasa, copacii plantati raman pe parcela respectiva.

La inceput sunt patru copaci plantati pe teren ca in figura alaturata:
{! problema/parcele2?parcele1.jpg 54% !}

Proprietarul doreste sa afle ce copaci trebuie sa mai planteze pe regiunea ((1,1) (2,3)) pentru ca aceasta sa devina frumoasa. El planteaza astfel un copac de inaltime 81 si unul de inaltime 3 pe parcele (2,3).

Proprietarul doreste sa afle ce copaci trebuie sa mai planteze pe regiunea ((1, 1)(2, 3)) pentru ca aceasta sa devina frumoasa. El planteaza astfel un copac de inaltime 81 si unul de inaltime 3 pe parcele (2, 3).

{! problema/parcele2?parcele2.jpg 54% !}

Apoi, acesta doreste sa "infrumuseteze" regiunea ((2,2) (3,4)) si va planta un copac pe parcela (3,4), de inaltime 3.

Apoi, acesta doreste sa "infrumuseteze" regiunea ((2, 2)(3, 4)) si va planta un copac pe parcela (3, 4), de inaltime 3.

{! problema/parcele2?parcele3.jpg 54% !}

In final, pentru a "infrumuseta" regiunea ((1,2) (2,4)), el nu trebuie sa planteze niciun copac.

In final, pentru a "infrumuseta" regiunea ((1, 2)(2, 4)), el nu trebuie sa planteze niciun copac.

{! problema/parcele2?parcele4.jpg 54% !}
== include(page="template/taskfooter" task_id="parcele2") ==

10459