Fişierul intrare/ieşire:	romb.in, romb.out	Sursă	ONI 2013, clasa a 10-a
Autor	Gheorghe Manolache	Adăugată de	FMI Ciprian Olariu •scipianus
Timp execuţie pe test	0.05 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Romb

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 4*X–3,4*X–2,4*X–1,4*X (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

Fişierul de intrare romb.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

În fişierul de ieşire romb.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

• -20000 < dx,dy,Cx,Cy < 20000; 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ă la distanţă mai mică de 10^-7 faţă de latura unui romb obţinut în ultima etapă.

Exemplu

Explicaţie

Numarul 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

Cum se trimit solutii?