ZParcurgere

z

==Include(page="template/taskheader" task_id="z")==

== include(page="template/taskheader" task_id="z") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| z.in | z.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="z") ==

==Include(page="template/raw")==
 
Z-parcurgere
 
 
 
 
 
Petrica are o tabla patratica de dimensiuni 2^n*2^n . Ar vrea sa scrie pe patratelele tablei numere naturale cuprinse intre 1 si 2^n*2^n conform unei parcurgeri mai deosebite pe care o numeste Z-parcurgere. O Z-parcurgere viziteaza recursiv cele patru cadrane ale tablei in ordinea: stanga-sus, dreapta-sus, stanga-jos, dreapta-jos. De exemplu, daca n=1 , ordinea vizitarii patratelelor de pe tabla este in forma de Z, ca in figura urmatoare:
 
 
|1 |2 |
 
|3 |4 |
 
 
 
 
Daca n=2 , Petrica va traversa patratelele in ordinea:
 
 
|1 |2 |5 |6 |
 
|3 |4 |7 |8 |
 
|9 |10 |13 |14 |
 
|11 |12 |15 |16 |
 
h2. Cerinta
 
La un moment dat Petrica ar vrea sa stie ce numar de ordine trebuie sa scrie conform Z-parcurgerii pe anumite patratele date prin coordonatele lor ( x, y ). Petrica incepe umplerea tablei intotdeauna din coltul din stanga-sus.
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare z.in se afla doua numere naturale N si K , unde N reprezinta faptul ca tabla are dimensiunea 2^n*2^n , iar K este numarul patratelelor pe care Petrica ar vrea sa stie ce numar va trebui sa scrie pe ele. Pe fiecare din urmatoarele K linii se afla cate doua numere naturale ( x, y ), care reprezinta linia, respectiv coloana unui patratel ales. A i+1 -a linie descrie al i -lea patratel ( i = 1, 2, ..., k ).
 
h2. Date de Iesire
 
Pe cele k linii ale fisierului de iesire z.out se va scrie cate un numar natural, corespunzator numarului pe care Petrica il va scrie pe patratelul ales. A i -a linie descrie al i -lea patratel ( i = 1, 2, ..., k ).
 
h2. Restrictii si precizari
 
. 1 <= N <= 15
 
. 1 <= K <= 1.000
 
. 1 <= x,y <= 2^n
 
h2. Exemplu
 
 
|z.in |z.out |
 
|2 2 |13 |
|3 3 |15 |
|4 3 | |
 
 
 
==Include(page="template/taskfooter" task_id="z")==