Diferențe pentru problema/romb2 între reviziile #3 si #4

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

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).
 
!problema/romb2?romb1.png!
!problema/romb2?romb2.png!
!problema/romb2?romb3.png!

h2. Date de intrare