Что спрашивают

A прибавляет 1. B умножает на 2. Найдите число программ из A в B, состоящих ровно из K команд. Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.

Три целых числа A, B и K: 1 ≤ A ≤ B ≤ 1000, 0 ≤ K ≤ 20. На сайте параметры читаются из ввода; на экзамене их берут из условия.

Приём решения

Числа на экране недостаточно для описания подзадачи: важно, сколько команд ещё осталось. Пусть f(x, left) — число программ из x до B за ровно left команд. Если left = 0, ответ равен 1 только при x = B. Если команд ещё осталось, но x уже не меньше B, продолжать бесполезно: обе команды увеличивают число. Иначе складываем f(x + 1, left − 1) и f(2 × x, left − 1). Запоминаем ответы для пар, а не только для x. Не засчитываем достижение цели раньше времени: нужна точная длина программы.

Разбор на примере

Ввод

1 4 2

Вывод

2
Разбор примера по шагам
Состояние или программаКак считаем
1, осталось 2выбираем A или B
2, осталось 1до 4 только умножением
4, осталось 01 подходящее завершение
итого2 программы

За две команды 1 превращается в 4 программами AB и BB. AAA тоже даёт 4, но состоит из трёх команд и здесь не учитывается. Для второго примера длина 3, поэтому подходят AAA и BAA: ответ снова 2.

Код на 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 int(x == b)
    if x >= b:
        return 0
    return ways(x + 1, left - 1) + ways(x * 2, left - 1)

print(ways(a, k))
#include <iostream>
#include <functional>
#include <cstring>
using namespace std;

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    static long long memo[1001][21];
    memset(memo, -1, sizeof(memo));
    function<long long(int,int)> ways = [&](int x, int left) -> long long {
        if (left == 0) return x == b;
        if (x >= b) return 0;
        auto &result = memo[x][left];
        if (result != -1) return result;
        result = ways(x + 1, left - 1) + ways(x * 2, left - 1);
        return result;
    };
    cout << ways(a, k) << "\n";
}

Типичные ошибки

  • Неверный ответ на цели

    На цели обычно есть одна пустая программа. Для ограничения на длину или число умножений дополнительно проверьте, что требуемый остаток равен нулю.

  • Потеря одной из команд

    Складывайте ответы для разных допустимых первых команд. Если команды приводят к одному числу, они всё равно задают разные записи программ.

  • Недостаточное состояние

    В ключ запоминания входят все данные, от которых зависят дальнейшие действия: число, оставшиеся команды или умножения, признак предыдущей команды.