Cerința
Se dă un număr natural n
despre care se cunoaște că este putere de 2
. Considerăm inițial șirul numerelor naturale de la 1
la n
așezate în ordine crescătoare. Notăm cu A
acest șir. Pornind de la acesta, se construiește un nou șir (să îl notăm cu B
) astfel: Primele n
elemente ale lui B
sunt chiar elementele șirului A
în aceeași ordine. Următoarele n/2
elemente ale lui B
sunt ultimele n/2
elemente ale lui A
dar scrise în ordine inversă (descrescător). Următoarele n/4
elemente ale lui B
sunt ultimele n/4
elemente ale lui A
scrise în ordine crescătoare, următoarele n/8
elemente ale lui B
sunt ultimele n/8
elemente ale lui A
scrise în ordine descrescătoare, și tot așa, cu fiecare putere de 2
(notată p
) ce apare la numitor, luăm ultimele n/p
elemente din A
și le adăugăm la finalul lui B
alternând ordinea de parcurgere, de la o putere la alta conform modului descris mai sus. Se mai să un număr poz
. Se cere determinarea numărului de pe poziția poz
din șirul B
.
Date de intrare
Fișierul beta.in
conține pe prima linie numerele naturale n
și poz
separate printr-un spațiu.
Date de ieșire
Fișierul beta.out
conține valoarea cerută. Dacă șirul B
are mai puțin de poz elemente se va scrie în fișier -1
.
Restricții și precizări
1 ≤ n ≤ 1.000.000.000
n
se dă putere de2
1 ≤ poz ≤ 2.000.000.000
- Pentru
55
de puncte avemn ≤ 100.000
Exemplu:
beta.in
8 13
beta.out
7
Explicație
Elementele șirului B
sunt, în ordine: 1 2 3 4 5 6 7 8 8 7 6 5 7 8 8