Question

У исполнителя есть три команды:
- **A.** Прибавить 2
- **B.** Прибавить 3
- **C.** Умножить на 2

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

Траектория вычислений — последовательность результатов после каждой команды. Например, для программы СВА при исходном числе 7 траектория: 14, 17, 19.

Accepted Answer

90

Answer

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

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

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

Рекурсивный случай: суммируем пути через все три команды.

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

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

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

Итоговый ответ — произведение этих двух значений.

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