| Условие задачи | | Прогресс |
|
Темы:
Рекурсия
Перебор
Рекурсивный перебор
В каком-то другом мире сегодня 31 декабря. Дед Кокованя решил приготовить многомерный бургер, который так любит Дарёна. Бургер уровня L (L - целое число, большее или равное 0) готовится следующим образом:
- Бургер нулевого уровня - это котлета.
- Бургер с уровнем
L (L >= 1) - это булочка, бургер с уровнем (L-1), котлета, бургер с другим уровнем (L-1) и еще одна булочка, уложенные вертикально в указанном порядке, считая снизу.
Например, бургер уровня 1 и бургер уровня 2 выглядят как БКККБ и ББКККБКБКККББ (повернутые на 90 градусов), где Б и К обозначают булочку и котлету.
Бургер, который приготовит дед Кокованя, - это бургер уровня N. Дарёна всегда съедает только Х слоев нижней части бургера (слой - это котлета или булочка). Сколько котлет она съест?
Входные данные
Программа получает на вход 2 целых числа через пробел: N и X (1 <= N <= 50, 1 <= X <= (общее количество слоев в бургере N-го уровня)).
Выходные данные
Выведите количество котлет в самых нижних X слоях, считая от нижней части бургера уровня N.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
2 7 |
4 |
В самых нижних 7 слоях бургера второго уровня ( ББКККБКБКККББ) находятся 4 котлеты. |
| 2 |
1 1 |
0 |
|
| 3 |
50 4321098765432109 |
2160549382716056 |
Бургер 50-го уровня довольно толстый настолько, что количество его слоев не укладывается в 32-битное целое число. |
| |
![]()
|