Районная олимпиада по информатике. 2015-2016 учебный год

Задача D. Последовательность

Ограничение по времени:

1 секунда

Ограничение по памяти:

64 мегабайта

Вам дана функция генерирующая последовательность: $F(1) = \{1\},$ $F(i) =\{F(i - 1),i,F(i - 1)\}.$ Например $F(3) = \{1,2,1,3,1,2,1\}$ генерирует эту последовательность. Для заданного целого числа $N$ найдите число стоящее на позиции $x$ в последовательности $F(N).$

Формат входного файла

Входные данные содержат два целых числа $1 \le N \le 1000$ и $1 \le x.$ Гарантируется, что $x$ не превосходит длины последовательности $F(N).$

Формат выходного файла

Выведите ответ к задаче.

Примеры:

Вход

3 4

Ответ

3

Комментарий/решение

def f(n):

if n > 1:

return [f(n-1), n, f(n-1)]

else:

return 1

n, m = map(int, input().split())

lst = f(n)

def f(x):

if isinstance(x, list):

for i in x:

yield from f(i)

else:

yield x

r = list(f(lst))

print(r[m-1])