| Fişierul intrare/ieşire: | banda.in, banda.out | Sursă | ONI 2008, clasa a 10-a |
| Autor | Zoltan Szabo | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 6144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Banda
Pe o masa orizontala se afla o banda super-flexibila, formata din 2n patratele de latura 1 cm. Grosimea benzii este de 1 mm. Patratelele sunt numerotate de la stanga la dreapta de la 1 la 2n. 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 2n-1 cm. Banda obtinuta se poate plia iar in doua. Acest procedeu se repeta de n ori, pana se obtine grosimea 2n 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 2n).
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:
Sa observam ca patratelul special este 2 si va ajunge in final pe pozitia 6.
Cerinta
Date fiind valorile n si k, scrieti un program care raspunde la o interogare de tipul 1 sau de tipul 2.
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.
Date de iesire
Fisierul banda.out va contine o singura linie pe care va fi scris un numar natural reprezentand rezultatul interogarii.
Restrictii si precizari
- 2 ≤ n ≤ 30
- 1 ≤ k, s, f ≤ 2n
- Pentru 30% dintre teste n ≤ 7. Pentru 50% dintre teste c = 1.
Exemplu
| banda.in | banda.out |
|---|---|
| 3 5 1 2 | 6 |
| 3 5 2 4 | 8 |
Explicatie
In exemple, banda de lungime 23 = 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).
