fractal

Fractal

== include(page="template/taskheader" task_id="fractal") ==

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

Poveste ...

Hilbert a gasit o curba care poate trece prin fiecare punct al spatiului, aceasta curba se bazeaza pe o constructie recursiva. Numim curba de ordin Hilbert de ordinul $K$ curba curba realizata dupa urmatoarele reguli ce trece prin fiecare nod al unei grile de $2^K^*2^K^$ noduri si trece prin noduri vecine ale grilei.
Curba Hilbert de ordinul 1 este o curba simpla:
!problema/fractal?image001.gif!
 
Vor fi descries in urmatoarele imagini trecerile de la o curba de ordin x la o curba de ordin x+1:
Ordin $1$ -> Ordin $2$
!problema/fractal?image001.gif! !problema/fractal?image002.gif! !problema/fractal?image003.gif! !problema/fractal?image004.gif! !problema/fractal?image005.gif!
Ordin $2$ -> Ordin $3$
!problema/fractal?image006.gif! !problema/fractal?image007.gif! !problema/fractal?image008.gif! !problema/fractal?image009.gif! !problema/fractal?image010.gif!
Ordin $3$ -> Ordin $4$
!problema/fractal?image011.gif! !problema/fractal?image012.gif! !problema/fractal?image013.gif! !problema/fractal?image014.gif! !problema/fractal?image015.gif!
Ordin $4$ -> Ordin $5$
!problema/fractal?image016.gif! !problema/fractal?image017.gif! !problema/fractal?image018.gif! !problema/fractal?image019.gif! !problema/fractal?image020.gif!
 
Se dau ca date de intrare din fisierul $fractal.in$ numerele $K, x$ si $y$, unde $K$ este ordinul unei curbe, iar $x$ si $y$ sunt coordanate intregi in interiorul unui patrat de dimensiune $2^K^*2^K^$. Se cere sa scrieti in fisierul de iesire $fractal.out$ in cati pasi se ajunge la coordonatele $(x,y)$ daca punctele din patrat sunt parcurse in ordinea data de curba Hilbert de ordin $K$.
 
h2. Restrictii si precizari
 
* $1 ≤ k ≤ 15$
* $1 ≤ x,y ≤ 2^K^$
* Coordonatele $x$ si $y$ sunt intre $1$ si $2^K^$ inclusiv ({$x$} reprezinta coloana, $y$ linia), iar coltul din stanga sus are coordonatele $(1,1)$.
 
h2. Exemple
 
table(example). |_. fractal.in |_. fractal.out |
| 1 1 1 | 0  |
| 3 2 3 | 13 |
| 2 4 1 | 15 |

h2. Cerinta

==Include(page="template/taskfooter" task_id="fractal")==

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

95