Что спрашивают
A прибавляет 1. B умножает на 2. Найдите число программ из A в B, траектория которых содержит C. Начальное и конечное числа тоже относятся к траектории. Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.
Три целых числа A, B и C: 1 ≤ A ≤ C ≤ B ≤ 60. На сайте параметры читаются из ввода; на экзамене их берут из условия.
Приём решения
Любая подходящая программа распадается на две части: от A до C и от C до B. Обе команды увеличивают число, поэтому C невозможно посетить второй раз. Каждую первую часть можно соединить с каждой второй: число программ равно ways(A, C) × ways(C, B). В функции ways(x, goal) получаем единицу при x = goal, ноль при x > goal и складываем ways(x + 1, goal) с ways(2 × x, goal) во всех остальных случаях. Если C совпадает с началом или концом, соответствующая часть пуста и даёт множитель 1.
Разбор на примере
Ввод
1 4 2
Вывод
4
| Состояние или программа | Как считаем |
|---|---|
| 1 → 2 | 2 способа |
| 2 → 4 | 2 способа |
| через 2 | 2 × 2 = 4 |
Из 1 в 2 можно попасть командами A или B: два варианта. Из 2 в 4 — AA или B: ещё два. Соединяем части и получаем четыре программы. Во втором примере до 4 из 2 есть две программы, а из 4 до 7 — только AAA: ответ 2.
Код на Python и C++
Функция возвращает количество продолжений, а не длину программы. Python запоминает значения через lru_cache, C++ — через таблицу с начальным значением −1. Число 0 в таблице уже является вычисленным ответом. Все ответы при данных ограничениях помещаются в знаковое 64-битное целое.
from functools import lru_cache
a, b, c = map(int, input().split())
lru_cache(None)
def ways(x, goal):
if x == goal:
return 1
if x > goal:
return 0
return ways(x + 1, goal) + ways(x * 2, goal)
print(ways(a, c) * ways(c, b))
<iostream>
<functional>
<cstring>
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c;
static long long memo[101][101];
memset(memo, -1, sizeof(memo));
function<long long(int,int)> ways = [&](int x, int goal) -> long long {
if (x == goal) return 1;
if (x > goal) return 0;
auto &result = memo[x][goal];
if (result != -1) return result;
return result = ways(x + 1, goal) + ways(x * 2, goal);
};
cout << ways(a, c) * ways(c, b) << "\n";
}
Типичные ошибки
- Неверный ответ на цели
На цели обычно есть одна пустая программа. Для ограничения на длину или число умножений дополнительно проверьте, что требуемый остаток равен нулю.
- Потеря одной из команд
Складывайте ответы для разных допустимых первых команд. Если команды приводят к одному числу, они всё равно задают разные записи программ.
- Недостаточное состояние
В ключ запоминания входят все данные, от которых зависят дальнейшие действия: число, оставшиеся команды или умножения, признак предыдущей команды.