Что спрашивают
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 |
|---|---|---|
| Без B | 41 прибавление | 1 |
| 101 | 110 | 6 |
| 102 | 120 | 2 |
| 103 | 130 | 1 |
| 104 | 140 | 1 |
| 112 | 121 | 2 |
| 113 | 131 | 1 |
| 114 | 141 | 1 |
| 123 | 132 | 1 |
Чтобы не потерять программы, разделим их по первой перестановке. До неё идут только прибавления, поэтому число перед первым 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))
<iostream>
<functional>
<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";
}
Типичные ошибки
- Неверный ответ на цели
На цели обычно есть одна пустая программа. Для ограничения на длину или число умножений дополнительно проверьте, что требуемый остаток равен нулю.
- Потеря одной из команд
Складывайте ответы для разных допустимых первых команд. Если команды приводят к одному числу, они всё равно задают разные записи программ.
- Недостаточное состояние
В ключ запоминания входят все данные, от которых зависят дальнейшие действия: число, оставшиеся команды или умножения, признак предыдущей команды.