Випробування автомата#122

Випробування автомата (Розбір)

Простежимо, як змінюється запас п'ятиужикових монет в автоматі після кожної покупки. Склянка коштує ужиків, решту автомат видає лише п'ятірками, а отримані п'ятірки залишає собі.

  • Заплатили монетою : решти немає, монета залишається в автоматі — запас зростає на .

  • Заплатили : решта , тобто одна монета — запас зменшується на .

  • Заплатили : решта , тобто дев'ять монет — запас зменшується на .

  • Заплатили : решта , тобто дев'ятнадцять монет — запас зменшується на .

Купюри самі по собі для решти не годяться, тому вони запас не поповнюють.

Отже, якщо початково завантажити монет, то після -ї покупки запас дорівнює x + P_i, де P_i — префіксна сума описаних змін. Автомат працює коректно, якщо запас ніколи не стає від'ємним, тобто

x + \min_i P_i \ge 0.

Звідси мінімальна кількість монет для завантаження:

x = \max\left(0,\; -\min_i P_i\right).

Реалізація — один прохід: ведемо поточну префіксну суму й запам'ятовуємо її мінімум. Складність — .

Зверніть увагу, що дивитися треба саме на мінімум по всіх префіксах, а не лише на кінцевий баланс: автомат може «просісти» посередині, навіть якщо в кінці монет вистачає.