Что спрашивают
A прибавляет 1. B умножает на 2. Найдите число программ из A в B, в которых нет двух команд B подряд. Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.
Два целых числа A и B: 1 ≤ A ≤ B ≤ 100. На сайте параметры читаются из ввода; на экзамене их берут из условия.
Приём решения
Чтобы понять, разрешено ли следующее умножение, нужно знать предыдущую команду. Пусть f(x, last) считает продолжения из x; last равен 1, если предыдущей командой было умножение, и 0 в остальных случаях. Прибавлять можно всегда: переходим в f(x + 1, 0). Умножать можно только при last = 0: тогда добавляем f(2 × x, 1). На цели получаем 1, за целью 0. В начале предыдущей команды нет, поэтому начинаем с last = 0. Ответы сохраняем по паре (x, last), не объединяя разные ограничения на следующий шаг.
Разбор на примере
Ввод
1 4
Вывод
3
| Состояние или программа | Как считаем |
|---|---|
| AAA | подходит |
| AB | подходит |
| BAA | подходит |
| BB | не подходит |
| итого | 3 программы |
Из 1 в 4 всего четыре программы: AAA, AB, BAA, BB. У последней два умножения подряд, поэтому остаются три. Во втором примере из 2 в 8 четыре программы без BB: AAAAAA, AAB, ABAA и BAAAA.
Код на 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, last):
if x == b:
return 1
if x > b:
return 0
result = ways(x + 1, 0)
if not last:
result += ways(x * 2, 1)
return result
print(ways(a, 0))
<iostream>
<functional>
<cstring>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
static long long memo[101][2];
memset(memo, -1, sizeof(memo));
function<long long(int,int)> ways = [&](int x, int last) -> long long {
if (x == b) return 1;
if (x > b) return 0;
auto &result = memo[x][last];
if (result != -1) return result;
result = ways(x + 1, 0);
if (!last) result += ways(x * 2, 1);
return result;
};
cout << ways(a, 0) << "\n";
}
Типичные ошибки
- Неверный ответ на цели
На цели обычно есть одна пустая программа. Для ограничения на длину или число умножений дополнительно проверьте, что требуемый остаток равен нулю.
- Потеря одной из команд
Складывайте ответы для разных допустимых первых команд. Если команды приводят к одному числу, они всё равно задают разные записи программ.
- Недостаточное состояние
В ключ запоминания входят все данные, от которых зависят дальнейшие действия: число, оставшиеся команды или умножения, признак предыдущей команды.