23.08 Прочие прототипы

Ключевое замечание, необходимое для решения задачи — заметим, что нет смысла рассматривать числа большие так как из них даже четырежды применив вторую операцию не получить число . Далее достаточно написать — количество программ заканчивающихся в числе и при этом использующие ровно шагов второго типа. База динамики . Переход в динамике: . Конечно стоит аккуратно проверять, что .

Решение динамикой

dp = [[0] * 5 for _ in range(16 * 20 + 1)]
dp[10][0] = 1
for cnt in range(5):
    for x in range(16 * 20 + 1):
        if x + 1 <= 16 * 20:
            dp[x + 1][cnt] += dp[x][cnt]
        if x % 2 == 0 and cnt + 1 < 5:
            dp[x // 2][cnt + 1] += dp[x][cnt]
print(sum(dp[20]))

Решение рекурсией

Мы используем рекурсивный подход с подсчетом количества программ. Идея решения заключается в том, что мы создаем функцию f(st, end, cnt), где:

- st — текущее число на экране,

- end — целевое число,

- cnt — количество применений второй команды (деления на 2) в текущей программе.

На каждом шаге выполняем следующие проверки:

1. Если текущее число st стало слишком большим (например, больше чем , что является грубой границей, чтобы рекурсия не ушла далеко в сторону), то возвращаем 0, так как дальнейшее применение команд не приведет к решению.

2. Если количество применений второй команды cnt превысило 4, возвращаем 0, так как по условию больше четырех применений этой команды быть не должно.

3. Если текущее число равно целевому (st == end), то мы нашли корректную программу, возвращаем 1, но при этом продолжаем проверять возможность применения второй команды еще раз, если число четное.

4. Если текущее число четное, можем применить обе команды:

- применяем первую команду (st+1) без увеличения счетчика cnt,

- применяем вторую команду (st//2) и увеличиваем cnt на 1, суммируем количество программ из этих двух вариантов.

5. Если текущее число нечетное, можем применить только первую команду (st+1).

Для ускорения вычислений мы используем кэширование результатов с помощью декоратора @lru_cache(None), чтобы не пересчитывать одни и те же вызовы функции.

Вызов f(10, 20, 0) запускает рекурсию с начального числа 10, целевого числа 20 и счетчика применений второй команды равного 0.

# Импортируем инструмент для кэширования вызовов функции
from functools import lru_cache

# Декоратор кэширует все результаты функции, чтобы не пересчитывать одинаковые параметры
@lru_cache(None)
def f(st, end, cnt):
    # Если текущее число стало слишком большим, путь невозможен
    if (st > 20*16):
        return 0
    # Если количество применений второй команды превысило 4, путь невозможен
    if (cnt > 4):
        return 0
    # Если текущее число равно целевому
    if (st == end):
        # Считаем этот путь, но продолжаем проверку возможности применения второй команды
        return 1 + f(st//2,end,cnt+1) + f(st+1, end, cnt)
    # Если число четное, можем применить обе команды
    if (st%2 == 0):
        # Первый вариант: прибавляем 1, счетчик второй команды не меняется
        # Второй вариант: делим на 2, увеличиваем счетчик второй команды
        return f(st+1, end, cnt) + f(st//2, end, cnt+1)
    else:
        # Если число нечетное, можно применить только прибавление 1
        return f(st+1, end, cnt)

# Вызываем функцию с начального числа 10, целевого 20, счетчик второй команды равен 0
# И выводим результат — количество программ, удовлетворяющих условиям
print(f(10,20,0))