Banda

banda

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

Pe o masa orizontala se afla o banda super-flexibila, formata din $2^n^$ patratele de latura $1 cm$. Grosimea benzii este de $1 mm$. Patratelele sunt numerotate de la stanga la dreapta de la $1$ la $2^n^$.  Aceasta banda se poate plia in doua, suprapunand o parte peste cealalta (stanga peste dreapta sau invers). Astfel, anumite pozitii se suprapun si se obtine grosime dubla si lungime $2^n-1^ cm$. Banda obtinuta se poate plia iar in doua. Acest procedeu se repeta de $n$ ori, pana se obtine grosimea $2^n^ mm$ si lungimea $1 cm$ (adica toata patratelele se vor suprapune, formand o singura coloana).
Folosind o pioneza, vom fixa de masa patratelul $k$ al benzii si aplicam procedeul de pliere descris mai sus, obtinand astfel o coloana a carei baza este patratelul $k$. in cadrul acestei coloane vom numerota pozitiile patratelelor de jos in sus de la $1$ la $2^n^$).
 
Exista doua tipuri de interogari posibile:
 
# Dat fiind un patratel (sa-l numim patratel special), sa se determine pozitia lui finala (pe coloana).
# Data fiind pozitia finala a patratelului special, sa se determine numarul sau.
 
De exemplu, pentru $n = 3$, si $k = 5$ vom obtine:
 
!problema/banda?desen.jpg!
 
Sa observam ca patratelul special este $2$ si va ajunge in final pe pozitia $6$.
 
h2. Cerinta
 
Date fiind valorile $n$ si $k$, scrieti un program care raspunde la o interogare de tipul $1$ sau de tipul $2$.

Poveste si cerinta...

h2. Date de intrare

Fisierul $banda.in$ contine $4$ linii. Pe prima linie este scris numarul natural $n$. Pe a doua linie este scris numarul natural $k$, reprezentand pozitia patratelului fixat. Pe cea de a treia linie este scrisa o cifra $c$ care poate fi $1$ sau $2$, indicand tipul interogarii. Daca cifra $c$ este $1$ pe cea de a patra linie este scris numarul natural $s$ reprezentand numarul patratelului special. Daca cifra $c$ este $2$ pe cea de a patra linie este scris un numar natural $f$ reprezentand pozitia finala a patratelului special.

Fisierul de intrare $banda.in$ ...

h2. Date de iesire

Fisierul $banda.out$ va contine o singura linie pe care va fi scris un numar natural reprezentand rezultatul interogarii.

In fisierul de iesire $banda.out$ ...

h2. Restrictii si precizari

h2. Restrictii

* $2 ≤ n ≤ 30$
* $1 ≤ k, s, f ≤ 2^n^$
* Pentru $30%$ dintre teste $n ≤ 7$. Pentru $50%$ dintre teste $c = 1$.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. banda.in |_. banda.out |

| 3
5
1
2
| 6 |
| 3
5
2
4
| 8
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicatie

In exemple, banda de lungime $2^3^ = 8 cm$ este fixata de masa pe pozitia $5$.
 
In primul exemplu, trebuie sa aflam pozitia finala a patratelului $2$ (aceasta este $6$).
 
In al doilea exemplu, se stie pozitia finala $4$, se cere numarul patratelului special ({$8$}).

...

== include(page="template/taskfooter" task_id="banda") ==