Войти Регистрация
Алгоритмы

167. Выдать сумму из кассет с остатками

Средняя

В банкомате len(notes) кассет: в кассете i лежит counts[i] купюр номиналом notes[i]. Клиент просит amount рублей.

Верните наименьшее число купюр, которым можно выдать ровно amount, или -1, если выдать нацело нельзя. Для amount = 0 ответ 0.

В работе: Банкомат или касса самообслуживания: в конце дня кассета с тысячами пуста, и сумму 3 500 приходится собирать из того, что осталось.

Пример 1

Ввод
notes = [5000, 2000, 1000]
counts = [3, 3, 0]
amount = 6000
Вывод
3

5000 + 1000 нельзя, тысяч нет. 2000 × 3 — три купюры.

Пример 2

Ввод
notes = [100, 50]
counts = [5, 5]
amount = 131
Вывод
-1

131 нацело не собрать — этот случай был в задаче на собеседовании.

Ограничения

  • 0 ≤ amount ≤ 2·10⁴
  • 1 ≤ число кассет ≤ 8
  • 1 ≤ notes[i] ≤ 5000, номиналы различны
  • 0 ≤ counts[i] ≤ 100
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def min_notes(notes, counts, amount):
Динамическое программированиеРюкзакцельn2

Источник: Яндекс, отчёт кандидата на Хабре, 2026. Условие пересказано своими словами.