Fişierul intrare/ieşire:banda.in, banda.outSursăONI 2008, clasa a 10-a
AutorZoltan SzaboAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.1 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/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:

  1. Dat fiind un patratel (sa-l numim patratel special), sa se determine pozitia lui finala (pe coloana).
  2. 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.inbanda.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content