.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » romb1

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
romb1


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
32MB / 16MB

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 dintre 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 4k 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 dintre 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

Pe prima linie a fişierului romb1.in se află numărul T de seturi de date de test. Pe fiecare dintre următoarele T linii se află câte un set de date de test cu valorile dx dy k Cx Cy, cu semnificaţia fin enunţ, separate prin câte un spaţiu.

Date de ieşire

Fişierul romb1.out va conţine T linii, pe linia i fiind scris răspunsul la întrebarea i, un număr natural reprezentând codul regiunii în care se află oraşul de coordonate date.

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

Exemple

romb1.inromb1.outExplicaţii
2 10 8 2 6 -2 12 16 3 -2 4 15 10 Numărul de seturi de date de test 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

autor: Prof. Gheorghe Manolache
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor