CS
Задачник Базовый курс EN

Задача

Без сдачи

динамика подсчёт вариантов префиксные суммы финансы

В кассе нет сдачи, и вы отсчитываете ровно N тенге монетами из кошелька. В нём монеты восьми достоинств — 1, 2, 5, 10, 20, 50, 100 и 200 тенге, — и каждого достоинства их ограниченное число: k1 монет по 1 тенге, k2 по 2 тенге и так далее. Сколькими способами можно отсчитать ровно N тенге?

Способы различаются только тем, сколько монет каждого достоинства вы отдаёте: монеты одного достоинства неотличимы, порядок не важен. Отдать ничего — тоже способ, если N = 0. Способов бывает очень много, выведите их число по модулю 109 + 7.

Вход

В первой строке N (0 ≤ N ≤ 105). Во второй — восемь чисел k1, …, k8 (0 ≤ ki ≤ 105): сколько в кошельке монет по 1, 2, 5, 10, 20, 50, 100 и 200 тенге.

Выход

Число способов по модулю 109 + 7.

Примеры

Пример 1

Вход
7
3 2 1 0 0 0 0 0
Выход
3

Пример 2

Вход
3
0 1 1 0 0 0 0 0
Выход
0

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
10 тестов

Разбор

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

1Подсказка 1

Начните с кошелька, где монет каждого достоинства сколько угодно. Монеты разрешаются по одной: ways[s] — сколько наборов из уже разрешённых монет дают s. Что меняется, когда монет достоинства c не больше k?

2Подсказка 2

С ограничением новый ответ — сумма k + 1 старых: new[s] = ways[s] + ways[s − c] + … + ways[s − k·c]. Если складывать честно, для полного кошелька это около N²/2 сложений на одни только монеты по 1 тенге. Сравните сумму для s с суммой для s − c: чем они отличаются?

3Идея

Суммы для s и для s − c — окна из k + 1 клеток с шагом c, сдвинутые на одну клетку. У них общие k слагаемых, поэтому

$$new[s] = new[s - c] + ways[s] - ways[s - (k + 1)c],$$

где последнее слагаемое вычитается, только если индекс неотрицателен. Это скользящее окно, или префиксные суммы вдоль каждого остатка по модулю c. На каждую сумму уходит одно сложение и одно вычитание, сколько бы монет ни было.

4Разбор

Состояние динамики — пара «сколько осталось набрать, какие достоинства уже разобраны», как в обычной задаче о наборах монет из статьи. Достоинства обрабатываем по очереди, каждое одним проходом по суммам от c до N. Новый массив считается из старого, поэтому храним оба: если писать в тот же массив, в окно попадут уже обновлённые клетки, и монеты достоинства c начнут считаться сверх лимита.

Третий тест — 1000 тенге при кошельке, где каждой монеты по тысяче: ограничения не мешают, и ответ совпадает с числом наборов из статьи, 321 335 886.

4+Решение
5Сложность

Восемь проходов по N + 1 суммам: O(8·N) времени, O(N) памяти.

6Типичные ошибки
  • Честная сумма окна. Верно, но четвёртый тест — полный кошелёк и N = 105: миллиарды сложений.
  • Лимиты не учтены. Если считать монеты неограниченными, не проходят первый пример и тесты с маленькими k.
  • Отрицательный остаток. После вычитания число может стать отрицательным. В Python оператор % вернёт неотрицательный остаток, а в Go и C++ остаток отрицательного числа отрицателен — прибавьте модуль.
  • Один массив вместо двух. Окно смешивает старые и новые значения — см. разбор.

Алгоритмы задачи

DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи
Каталог алгоритмов