Что спрашивают

A прибавляет 1. B меняет местами цифры десятков и единиц, только если цифра десятков меньше цифры единиц. Найдите число программ, переводящих A в B. Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.

Два целых числа A и B: 100 ≤ A ≤ B ≤ 199. На сайте параметры читаются из ввода; на экзамене их берут из условия.

Приём решения

Последняя сотня сохраняется. Пусть f(x) — сколько программ доводят число x до B. Из B подходит одна пустая программа; из x > B нет ни одной. Сначала считаем f(x + 1). Если десятки меньше единиц, добавляем f(x + 9 × (единицы − десятки)): именно на столько число увеличивается после обмена. Каждая программа начинается с одной определённой команды, поэтому ответы для разных первых команд складываются. Запоминание f(x) позволяет не решать одну и ту же подзадачу снова.

Разбор на примере

Ввод

100 141

Вывод

16
Разбор примера по шагам
Перед первым BПосле BПродолжений до 141
Без B41 прибавление1
1011106
1021202
1031301
1041401
1121212
1131311
1141411
1231321

Чтобы не потерять программы, разделим их по первой перестановке. До неё идут только прибавления, поэтому число перед первым B однозначно задаёт начало программы. В таблице перечислены все допустимые первые перестановки; правый столбец — число продолжений до 141 после неё. Ещё одна программа состоит только из 41 прибавления. Складываем: 1 + 6 + 2 + 1 + 1 + 2 + 1 + 1 + 1 = 16.

Например, первая перестановка в 101 даёт 110, а из 110 до 141 есть шесть продолжений. Перестановка в 104 даёт 140: дальше остаётся единственное прибавление. Для второго примера, 101 → 110, есть две программы: девять прибавлений и одна перестановка.

Код на Python и C++

Функция возвращает количество продолжений, а не длину программы. Python запоминает значения через lru_cache, C++ — через таблицу с начальным значением −1. Число 0 в таблице уже является вычисленным ответом. Все ответы при данных ограничениях помещаются в знаковое 64-битное целое.

from functools import lru_cache

a, b = map(int, input().split())

@lru_cache(None)
def ways(x):
    if x == b:
        return 1
    if x > b:
        return 0
    result = ways(x + 1)
    tens, units = x // 10 % 10, x % 10
    if tens < units:
        result += ways(x + 9 * (units - tens))
    return result

print(ways(a))
#include <iostream>
#include <functional>
#include <cstring>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    static long long memo[200][1];
    memset(memo, -1, sizeof(memo));
    function<long long(int)> ways = [&](int x) -> long long {
        if (x == b) return 1;
        if (x > b) return 0;
        auto &result = memo[x][0];
        if (result != -1) return result;
        result = ways(x + 1);
        int tens = x / 10 % 10, units = x % 10;
        if (tens < units) result += ways(x + 9 * (units - tens));
        return result;
    };
    cout << ways(a) << "\n";
}

Типичные ошибки

  • Неверный ответ на цели

    На цели обычно есть одна пустая программа. Для ограничения на длину или число умножений дополнительно проверьте, что требуемый остаток равен нулю.

  • Потеря одной из команд

    Складывайте ответы для разных допустимых первых команд. Если команды приводят к одному числу, они всё равно задают разные записи программ.

  • Недостаточное состояние

    В ключ запоминания входят все данные, от которых зависят дальнейшие действия: число, оставшиеся команды или умножения, признак предыдущей команды.