Fişierul intrare/ieşire:z.in, z.outSursăGrigore Moisil By Net 2006
AutorMihai PantisAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

ZParcurgere

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

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 2N*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 ieşire

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

Restricţii

  • 1 ≤ N ≤ 15
  • 1 ≤ K ≤ 1 000
  • 1 ≤ x, y ≤ 2N

Exemplu

z.inz.out
2 2
3 3
4 3
13
15
Trebuie sa te autentifici pentru a trimite solutii. Click aici