Question

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

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

Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 26 и при этом траектория вычислений содержит число 12 и не содержит числа 22?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Accepted Answer

30

Answer

Идея решения: использовать динамическое программирование, где $R(n)$ — количество программ, преобразующих 2 в $n$, с учётом ограничений на траекторию.

Обозначим $R(n)$ как число способов получить $n$ из 2. Рекуррентные соотношения зависят от делимости $n$:

1. Если $n$ не делится ни на 2, ни на 3: $R(n) = R(n - 1)$ (только прибавление 1).
2. Если $n$ делится на 2, но не на 3: $R(n) = R(n - 1) + R(n / 2)$.
3. Если $n$ делится на 3, но не на 2: $R(n) = R(n - 1) + R(n / 3)$.
4. Если $n$ делится на 2 и на 3: $R(n) = R(n - 1) + R(n / 2) + R(n / 3)$.

Вычислим значения до 12:

$$R(2) = 1$$
$$R(3) = R(2) + R(1) = 1 + 0 = 1$$
$$R(4) = R(3) + R(2) = 1 + 1 = 2$$
$$R(5) = R(4) = 2$$
$$R(6) = R(5) + R(2) + R(3) = 2 + 1 + 1 = 4$$
$$R(7) = R(6) = 4$$
$$R(8) = R(7) + R(4) = 4 + 2 = 6$$
$$R(9) = R(8) + R(3) = 6 + 1 = 7$$
$$R(10) = R(9) + R(5) = 7 + 2 = 9$$
$$R(11) = R(10) = 9$$
$$R(12) = R(11) + R(6) + R(4) = 9 + 4 + 2 = 15$$

Поскольку траектория должна содержать 12, все пути от 2 к 26 проходят через 12. Это означает, что ответ равен произведению количества путей от 2 к 12 и количества путей от 12 к 26 (без прохождения через 22).

Вычислим пути от 12 к 26, исключив 22:

$$R(13) = R(12) = 15$$
$$R(14) = R(13) = 15$$
$$\ldots$$
$$R(21) = 15$$
$$R(22) = 0 	ext{ (исключаем)}$$
$$R(23) = 0$$
$$R(24) = R(23) + R(12) = 0 + 15 = 15$$
$$R(25) = R(24) = 15$$
$$R(26) = R(25) + R(13) = 15 + 15 = 30$$

Альтернативное решение на Python:

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

print(f(2, 12) * f(12, 26))
```

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