== include(page="template/taskheader" task_id="banda") ==
Poveste si cerinta...
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$.
h2. Date de intrare
Fisierul de intrare $banda.in$ ...
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.
h2. Date de iesire
In fisierul de iesire $banda.out$ ...
Fisierul $banda.out$ va contine o singura linie pe care va fi scris un numar natural reprezentand rezultatul interogarii.
h2. Restrictii
h2. Restrictii si precizari
* $... ≤ ... ≤ ...$
* $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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 3
5
1
2
| 6 |
| 3
5
2
4
| 8
|
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") ==
