== include(page="template/taskheader" task_id="romb2") ==
*Notă:* Aceasta este o extensie a problemei "Romb":http://www.infoarena.ro/problema/romb de la ONI 2013, clasa a 10-a. Primele 10 teste coincid cu cele de la ONI, iar ultimele 10 teste sunt mari. Pentru punctaj maxim, încercați să rezolvați problema iterativ, folosind doar tipuri de date întregi și fără împărțiri.
*Notă:* Aceasta este o extensie a problemei "Romb":http://www.infoarena.ro/problema/romb de la ONI 2013, clasa a 10-a. Primele 10 teste sunt cele de la ONI, iar ultimele 10 teste sunt mari. *Pentru punctaj maxim,* încercați să eliminați, în această ordine a priorităților: tipurile de date reale, împărțirile în bucla critică, recursivitatea, înmulțirile în bucla critică.
Noul împărat INFO al țării ONI2013 a decis să împartă țara în regiuni codificate după un algoritm stabilit prin decret. Țara are formă de romb, având centrul în punctul de coordonate (0,0) și lungimile semi-diagonalelor $dx$ și $dy$ (ca în figura 1).
Împăratul alege un număr [$k$], reprezentând numărul de etape de parcurs, astfel:
* în prima etapă, rombul inițial este împărțit în patru regiuni egale, în formă de romb, fiecare latură fiind jumătate din latura rombului inițial;
* în fiecare din celelalte $k$ - 1 etape, orice romb rezultat la etapa precedentă este împărțit în alte patru romburi egale, așa cum este descris în prima etapă.
Astfel, după $k$ etape vom avea în total $4[^k^]$ regiuni egale, în formă de romb. Codificarea regiunilor este făcută astfel:
* în prima etapă, rombul inițial se împarte în patru regiuni, codificate în sens trigonometric cu valorile 1, 2, 3 și 4 (ca în figura 2);
* în fiecare din celelalte etape, se reface codificarea, astfel: dacă rombul anterior avea la etapa precedentă codul [$X$], cele patru romburi obținute după divizarea curentă vor avea acum codurile $4X - 3, 4X - 2, 4X - 1, 4X$ (figura 3).
!problema/romb2?romb1.png!
!problema/romb2?romb2.png!
!problema/romb2?romb3.png!
h2. Cerință
Împăratul dorește să știe după cele $k$ etape, care este codul regiunii unde se află un oraș dat prin coordonatele $(Cx, Cy)$.
h2. Date de intrare
Fișierul de intrare $romb2.in$ ...
Pe prima linie a fișierului $romb2.in$ se află numărul $T$ de întrebări (seturi de date de test). Pe fiecare din următoarele $T$ linii se află câte un set de date de test cu valorile $dx, dy, k, Cx, Cy$, cu semnificația anterioară, separate prin câte un spațiu.
h2. Date de ieșire
În fișierul de ieșire $romb2.out$ ...
Fișierul $romb2.out$ va conține $T$ linii, pe fiecare linie $i$ fiind răspunsul la întrebarea [$i$], un număr natural reprezentând codul regiunii în care se află orașul de coordonate date (pentru testul [$i$]).
h2. Restricții
h2. Restricții și precizări
* $... ≤ ... ≤ ...$
* $-20.000 < dx, dy, Cx, Cy < 20.000; 0 < k < 30; 0 < T < 100.000;$
* Pentru $50%$ din teste, $0 < k < 20; 0 < T < 10;$
* $dx$ și $dy$ sunt numere naturale, iar $Cx$ și $Cy$ sunt numere întregi;
* Se garantează că punctul de coordonate $(Cx, Cy)$ nu se află pe granița dintre două regiuni sau pe granița țării. *(Formularea originală de la ONI:* Se garantează că punctul de coordonate $(Cx, Cy)$ nu se află la distanță mai mică de 10^-7^ față de latura unui romb obținut în ultima etapă).
h2. Exemplu
table(example).
|_. romb2.in |_. romb2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. romb2.in |_. romb2.out |_. Explicații |
| 2
10 8 2 6 -2
12 16 3 -2 4
| 15
10
| Numărul de teste este T=2.
Orașul de coordonate (6, -2) se află în regiunea codificată cu 15
Orașul de coordonate (-2, 4) se află în regiunea codificată cu 10
|
== include(page="template/taskfooter" task_id="romb2") ==
