Question

У исполнителя Прибавитель две команды:

1. **Прибавь 1** — увеличивает число на 1.
2. **Увеличь старшую цифру на 1** — увеличивает на 1 левую (старшую) цифру числа. Например, 23 становится 33. Если старшая цифра равна 9, команда число не меняет.

Программа — это последовательность команд. Найти количество программ, которые число 35 преобразуют в число 57.

Accepted Answer

20

Answer

Идея решения: проанализировать, сколько раз можно применить команду 2 (увеличение старшей цифры), а остальное заполнить командой 1.

**Анализ команды 2:**

Исходное число 35 имеет старшую цифру 3. Команда 2 увеличивает её на 1, превращая 35 в 45. Применив команду 2 ещё раз, получим 55. Третье применение даст 65, что уже превышает целевое число 57. Поэтому команду 2 имеет смысл использовать не более двух раз.

**Случай 1: команда 2 используется 2 раза**

После двух применений команды 2 число 35 становится 55. Нужно добавить ещё 2 единицы, используя команду 1 дважды. Всего 4 команды, из которых 2 — это команда 2, остальные 2 — команда 1.

Количество способов расставить две команды 2 среди 4 позиций: $\binom{4}{2} = 6$.

**Случай 2: команда 2 используется 1 раз**

После одного применения команды 2 число 35 становится 45. Нужно добавить ещё 12 единиц, используя команду 1 двенадцать раз. Всего 13 команд, из которых 1 — это команда 2, остальные 12 — команда 1.

Количество способов расставить одну команду 2 среди 13 позиций: $\binom{13}{1} = 13$.

**Случай 3: команда 2 не используется**

Нужно увеличить 35 на 22, используя только команду 1. Это даёт единственную программу из 22 команд 1.

Количество программ: 1.

**Итого:** $6 + 13 + 1 = 20$.

```python
def f(x, y):
    if x == y:
        return 1
    if x > y:
        return 0
    return f(x + 1, y) + f(x + 10, y)

print(f(35, 57))
```

Функция `f(x, y)` подсчитывает количество программ, преобразующих число `x` в число `y`. На каждом шаге либо применяем команду 1 (переход к `x + 1`), либо команду 2 (переход к `x + 10`, так как увеличение старшей цифры на 1 для числа вида `ab` даёт `(a+1)b = 10(a+1) + b = 10a + 10 + b = x + 10`).

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