Fişierul intrare/ieşire:	z.in, z.out	Sursă	Grigore Moisil By Net 2006
Autor	Mihai Pantis	Adăugată de
Timp execuţie pe test	0.025 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	1/5

Vezi solutiile trimise | Statistici

ZParcurgere

Z-parcurgere

Petrica are o tabla patratica de dimensiuni 2ⁿ*2ⁿ. Ar vrea sa scrie pe patratelele tablei numere naturale cuprinse intre 1 si 2ⁿ*2ⁿ 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:

Daca n=2, Petrica va traversa patratelele in ordinea:

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.

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*2n , 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 ).

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

Restrictii si precizari

. 1 <= N <= 15

. 1 <= K <= 1.000

. 1 <= x,y <= 2^n

Exemplu

Cum se trimit solutii?