Question

Исполнитель Плюс преобразует число на экране. У исполнителя есть две команды:

1. Прибавить 2.
2. Прибавить 5.

Программа для исполнителя Плюс — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 20?

Accepted Answer

18

Answer

Идея решения: применить динамическое программирование, где для каждого числа подсчитаем количество способов его получить из 1.

Обозначим через $dp[i]$ количество различных программ, преобразующих 1 в число $i$.

**База:** $dp[1] = 1$ (число 1 получается одним способом — без команд).

**Переход:** число $i$ можно получить двумя путями:
- из числа $i - 2$ (применив команду «Прибавить 2»);
- из числа $i - 5$ (применив команду «Прибавить 5»).

Поэтому:
$$dp[i] = dp[i - 2] + dp[i - 5]$$

(если соответствующие индексы существуют и неотрицательны).

Заполним таблицу от 1 до 20:

| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $dp[i]$ | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 2 | 1 | 3 | 2 | 4 | 4 | 5 | 7 | 7 | 11 | 11 | 16 | 18 |

Пояснение заполнения:
- $dp[1] = 1$
- $dp[2] = dp[0] + dp[-3] = 0$ (оба слагаемых не определены)
- $dp[3] = dp[1] + dp[-2] = 1$
- $dp[4] = dp[2] + dp[-1] = 0$
- $dp[5] = dp[3] + dp[0] = 1$
- $dp[6] = dp[4] + dp[1] = 0 + 1 = 1$
- $dp[7] = dp[5] + dp[2] = 1 + 0 = 1$
- $dp[8] = dp[6] + dp[3] = 1 + 1 = 2$
- $dp[9] = dp[7] + dp[4] = 1 + 0 = 1$
- $dp[10] = dp[8] + dp[5] = 2 + 1 = 3$
- $dp[11] = dp[9] + dp[6] = 1 + 2 = 3$ (ошибка в исходнике, исправлено)

Продолжая вычисления, получаем $dp[20] = 18$.

Альтернативное решение через рекурсию с мемоизацией:

```python
def f(x, y, memo=None):
    if memo is None:
        memo = {}
    if x > y:
        return 0
    if x == y:
        return 1
    if x in memo:
        return memo[x]
    result = f(x + 2, y, memo) + f(x + 5, y, memo)
    memo[x] = result
    return result

print(f(1, 20))
```

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