Question

Исполнитель преобразует число на экране. Доступны три команды:

1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 3.

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

Accepted Answer

6006

Answer

Идея решения: разбить задачу на два этапа — путь от 3 до 10 и путь от 10 до 25, исключив траектории, проходящие через 17.

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

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

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

Ответ — произведение количества путей от 3 до 10 и от 10 до 25:

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

result = f(3, 10) * f(10, 25)
print(result)
```

Вычисляем:
- `f(3, 10)` — количество путей от 3 до 10 без прохождения через 17;
- `f(10, 25)` — количество путей от 10 до 25 без прохождения через 17.

Произведение даёт общее количество программ, удовлетворяющих всем условиям.

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