power поначалу равна 0. Находясь на ступеньке i, за один ход он может:
- спуститься на ступеньку i - 1. Так нельзя ходить со ступеньки 0 и нельзя делать два спуска подряд;
- прыгнуть вверх на ступеньку i + 2^power, после чего power увеличивается на 1.
Маршрут — это любая последовательность ходов, в том числе пустая. Посчитайте, сколько существует маршрутов, после которых кузнечик стоит на ступеньке target. Маршрут может проходить через target и раньше: например, если кузнечик попал на target, ушёл и вернулся, это ещё один маршрут.target=2 → 4
Подходят четыре маршрута: прыжок 1 → 2; шаг вниз 1 → 0, прыжок 0 → 1, прыжок 1 → 3, шаг вниз 3 → 2; прыжок 1 → 2, шаг вниз 2 → 1, прыжок 1 → 3, шаг вниз 3 → 2; шаг вниз 1 → 0, прыжок 0 → 1, шаг вниз 1 → 0, прыжок 0 → 2.
target=0 → 2
Либо сразу шаг вниз 1 → 0, либо шаг вниз, прыжок на 1 обратно на ступеньку 1 и снова шаг вниз. Дальше прыжки уже слишком длинные, чтобы вернуться.
target=7 → 4
Ступенька 7 = 1 + 1 + 2 + 4 − 1: три прыжка и ровно один шаг вниз, который можно вставить в любой из четырёх промежутков вокруг прыжков.
target ≤ 10⁹target=2
4
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 81 тест на сервере, включая скрытые.