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