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

Date de intrare

Fișierul de intrare romb2.in ...

Date de ieșire

În fișierul de ieșire romb2.out ...

Restricții

• ... ≤ ... ≤ ...

Exemplu

Explicație

...