Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Новогодняя ночь — это самое интересное и захватывающее событие праздника, а особенно интересной она становится, если наблюдать за ней, сидя около круглосуточных магазинов.
Именно так и поступил математик Константин Трезвенник, а наблюдал он именно за этим самым входом, ведь заметил интересную, для себя, математическую задачку:
Вот очередной человек подходит к магазину на расстояние N шагов (до этого момента математик не мог различить фигуру в пурге) и примерно раз в секунду делает шаг: либо вперед, ближе к магазину, либо назад, от него.
Таким образом он заходит в магазин за ровно K шагов. Вы спросите: «В чем же математический интерес?», а вы попробуйте посчитать, сколькими путями человек мог дойти до магазина.
Входные данные: Два числа N и K через пробел. 1≤N≤K≤40
Выходные данные: Количество возможных путей
Пример входных данных:
Пояснение: Способов добраться до магазина за 4 шага всего 4: -+++, +-++, ++-+, +++- однако в последних двух мы попадаем в магазин, а затем выходим из него и попадаем заново в него же, однако Константин перестал бы считать после первого захода в магазин, поэтому они нам не подходят Для отправки решений необходимо выполнить вход.
|