Fişierul intrare/ieşire:romb2.in, romb2.outSursăONI 2013
AutorGheorghe ManolacheAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Romb2 (clasele 9-10)

Notă: Aceasta este o extensie a problemei Romb de la ONI 2013, clasa a 10-a. Primele 10 teste sunt 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 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 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

romb2.inromb2.outExplicaţii
2
10 8 2 6 -2
12 16 3 -2 4
15
10
Numărul 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
Trebuie sa te autentifici pentru a trimite solutii. Click aici