Fișierul intrare/ieșire	romb2.in, romb2.out	Sursă	ONI 2013
Autor	Gheorghe Manolache	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.1 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	2.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Romb2 (clasele 9-10)

Notă: Aceasta este o extensie a problemei 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ă 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).

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

Date de intrare

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.

Date de ieșire

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

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

Exemplu