Банкомат работает с купюрами пяти номиналов: 20, 50, 100, 200, 500 (именно в
таком порядке по индексам 0..4). Нужно реализовать тип ATM с двумя операциями.
// NewATM создаёт пустой банкомат.
func NewATM() *ATM
// Deposit вносит купюры: counts[i] — сколько купюр i-го номинала добавить.
// Длина counts всегда 5.
func (a *ATM) Deposit(counts []int)
// Withdraw выдаёт сумму amount, используя как можно больше крупных купюр.
// Возвращает срез из 5 чисел — сколько купюр каждого номинала выдано.
// Если выдать сумму такой стратегией нельзя — возвращает []int{-1} и НЕ
// меняет содержимое банкомата.
func (a *ATM) Withdraw(amount int) []int
Правила выдачи
- Жадность от крупных к мелким: сначала берём максимум купюр по 500, затем по
200 и так далее. Если по этой схеме остаток не обнуляется — операция
невозможна, возвращается
[-1], а купюры в банкомате остаются на месте.
- При успехе выданные купюры списываются со счётчиков банкомата.
Пример
atm := NewATM()
atm.Deposit([]int{0,0,1,2,1}) // 1×100, 2×200, 1×500
atm.Withdraw(600) → [0,0,1,0,1] // 500 + 100
atm.Deposit([]int{0,1,0,1,1})
atm.Withdraw(600) → [-1] // жадно: 500 и 50, остаток 50 набрать нечем
atm.Withdraw(550) → [0,1,0,0,1] // 500 + 50
Ограничения
amount и число купюр могут быть большими (до ~10⁹ и 10⁹ штук) — нужен
достаточно широкий целый тип.- Операций может быть много; каждая должна работать за O(1) (пять номиналов).
Устно: почему жадность «крупные вперёд» для этих номиналов — часть
постановки, а не оптимизация? Приведи номиналы, где она дала бы [-1], хотя
размен существует.