Question

Исполнитель преобразует число на экране. Доступны три команды:
1. Прибавить 2
2. Прибавить 3
3. Умножить на 3

Программа — последовательность команд. Найти количество программ, которые:
- начинают с числа 3
- заканчиваются числом 25
- траектория содержит число 15
- траектория не содержит число 9

Accepted Answer

63

Answer

Идея решения: разбить задачу на два этапа — путь от 3 до 15 (избегая 9) и путь от 15 до 25, затем перемножить количества.

Используем рекурсию с мемоизацией. Функция `f(x, y)` подсчитывает количество способов достичь число `y` из числа `x`, не посещая 9 и не превышая `y`.

Базовые случаи:
- если `x > y` или `x == 9`, то способов нет (возвращаем 0);
- если `x == y`, то найден один способ (возвращаем 1).

Рекурсивный случай: из `x` можно перейти в `x + 2`, `x + 3` или `x * 3`, суммируя количества путей из каждого нового состояния.

Ответ получается как произведение:
- количество путей от 3 до 15 (без 9)
- количество путей от 15 до 25 (без 9)

```python
def f(x, y):
    if x > y or x == 9:
        return 0
    if x == y:
        return 1
    return f(x + 2, y) + f(x + 3, y) + f(x * 3, y)

print(f(3, 15) * f(15, 25))
```

Первый вызов `f(3, 15)` считает пути от 3 до 15, избегая 9. Второй вызов `f(15, 25)` считает пути от 15 до 25, также избегая 9. Произведение дает общее количество программ, удовлетворяющих всем условиям.

Задание №23Алгоритмы и исполнителиЕГЭ по информатике