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