Разбор задачи «Склад жетонов»

Идея задачи

У нас есть жетоны номиналов 1, 3, 6, 10 и 15. Для каждого значения n нужно найти минимальное количество жетонов, которыми можно набрать эту сумму.

На первый взгляд кажется, что здесь подойдет обычная жадность: брать как можно больше жетонов по 15, потом по 10, потом по 6 и так далее. Но такая идея работает не всегда.

Например:

• 20 = 10 + 10 — это 2 жетона,
• а жадный подход мог бы взять 15, а затем добрать 3 + 1 + 1, то есть уже 4 жетона.

Еще пример:

• 23 = 10 + 10 + 3 — это 3 жетона,
• а жадный подход через 15 даст 15 + 6 + 1 + 1, то есть 4 жетона.

Значит, простая жадность не подходит.

Первый шаг: динамика для маленьких сумм

Если бы n было маленьким, задачу можно было бы решить обычным динамическим программированием.

Пусть dp[x] — минимальное количество жетонов, нужное для суммы x.

Тогда переход такой:

• пробуем взять жетон 1, 3, 6, 10 или 15,
• и смотрим, можно ли улучшить dp[x] через dp[x - coin] + 1.

Формально:

dp[x] = min(dp[x - 1] + 1, dp[x - 3] + 1, dp[x - 6] + 1, dp[x - 10] + 1, dp[x - 15] + 1)

если соответствующий индекс не отрицательный.

Но в условии n может быть очень большим, поэтому строить динамику до 10^9 нельзя.

Главная идея

Заметим, что самый большой номинал — 15. Поэтому для больших n оптимальный ответ почти всегда будет использовать много жетонов по 15.

Пусть

• q = n // 15 — сколько раз число 15 целиком помещается в n,
• r = n % 15 — остаток.

Тогда естественный кандидат на ответ:

• взять q жетонов по 15,
• остаток r добрать оптимально.

То есть один вариант:

q + dp[r]

Но выше мы уже увидели, что иногда брать слишком много жетонов по 15 невыгодно. Может быть полезно отказаться от одной монеты 15 и вместо этого оптимально набрать сумму r + 15.

Тогда второй вариант:

(q - 1) + dp[r + 15]

И вот здесь ключевое наблюдение:

для этой задачи достаточно проверить только эти два случая.

Почему?

Потому что если мы уменьшаем число жетонов 15 больше чем на один, то остаток увеличивается еще сильнее, а все нужные локальные улучшения уже успевают проявиться в диапазоне до 30.

Поэтому достаточно заранее посчитать dp[x] только для x от 0 до 30, а затем для каждого запроса взять минимум из двух вариантов.

Почему хватает диапазона до 30

Если мы взяли:

• либо q жетонов по 15, тогда остаток равен r, где 0 <= r < 15,
• либо q - 1 жетонов по 15, тогда нужно добрать r + 15, а это уже число от 15 до 29.

Значит, нам нужны ответы только для значений от 0 до 29. Для надежности удобно посчитать до 30 включительно.

Это делает решение очень быстрым.

Алгоритм

Для каждого теста:

1. считаем q = n // 15 и r = n % 15,
2. первый кандидат: q + dp[r],
3. если q > 0, второй кандидат: (q - 1) + dp[r + 15],
4. выводим минимум.

Корректность

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

Рассмотрим произвольную сумму n.

Пусть в некотором оптимальном решении используется много жетонов по 15. Тогда естественно сравнить его с разложением

• либо с максимально возможным количеством жетонов 15,
• либо с таким же разложением, но с уменьшением числа жетонов 15 на один.

Остаток после выбора максимального числа жетонов 15 всегда меньше 15, то есть находится в диапазоне, который мы полностью перебрали динамикой.

Если максимальное число жетонов 15 приводит к неудачному локальному выбору, то проблема проявляется в комбинации суммы 15 + r. Именно поэтому достаточно проверить вариант, где один жетон 15 убран, а остаток увеличен на 15.

Так как для всех чисел до 30 значение dp найдено точно, оба кандидата считаются точно. Минимум из них и есть оптимальный ответ.

Сложность

Предподсчет:

• O(30 * 5)

Обработка одного теста:

• O(1)

Итоговая сложность:

• O(t) после очень маленького предподсчета.

Память:

• O(30)

Реализация на C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;

    vector<int> coins = {1, 3, 6, 10, 15};
    const int LIM = 30;
    const int INF = 1e9;

    vector<int> dp(LIM + 1, INF);
    dp[0] = 0;

    for (int s = 1; s <= LIM; s++) {
        for (int c : coins) {
            if (s >= c) {
                dp[s] = min(dp[s], dp[s - c] + 1);
            }
        }
    }

    while (t--) {
        long long n;
        cin >> n;

        long long q = n / 15;
        int r = n % 15;

        long long ans = q + dp[r];

        if (q > 0) {
            ans = min(ans, (q - 1) + (long long)dp[r + 15]);
        }

        cout << ans << '\n';
    }

    return 0;
}

Реализация на Python

t = int(input())

coins = [1, 3, 6, 10, 15]
LIM = 30
INF = 10**9

dp = [INF] * (LIM + 1)
dp[0] = 0

for s in range(1, LIM + 1):
    for c in coins:
        if s >= c:
            dp[s] = min(dp[s], dp[s - c] + 1)

for _ in range(t):
    n = int(input())

    q = n // 15
    r = n % 15

    ans = q + dp[r]

    if q > 0:
        ans = min(ans, q - 1 + dp[r + 15])

    print(ans)

Частые ошибки

1. Пытаться решить задачу чистой жадностью

Это ломается, например, на 20 и 23.

2. Считать динамику до очень большого n

Такое решение не пройдет по времени и памяти, если n велико.

3. Проверять только вариант q + dp[r]

Этого недостаточно. Иногда нужно убрать один жетон 15 и добрать более удачной комбинацией.

4. Забыть случай q = 0

Тогда вариант (q - 1) + dp[r + 15] проверять нельзя.

Небольшой вывод

Это хорошая задача на сочетание двух идей:

• маленькая динамика,
• наблюдение о том, что большие значения можно свести к нескольким локальным случаям.

Именно такие задачи полезны тем, что здесь недостаточно просто знать dp или просто знать жадность — нужно заметить структуру номиналов и аккуратно использовать ее в решении.