Розрахунок#170

Розрахунок (Editorial)

Спокуса розв'язати задачу простою жадібністю («беремо якнайбільше монет по 50, потім по 20, і так далі») — і саме тут ховається пастка. Номінал не ділиться націло на , тому жадібність може завести в глухий кут.

Контрприклад: треба заплатити копійок, у наявності одна монета по і три по . Жадібність візьме монету , а решту набрати вже нічим. Правильна ж відповідь — три монети по .

Натомість зауважмо, що для номіналів жадібність коректна: тут кожен наступний номінал ділиться на попередній (5 \mid 10 \mid 20), а для такої системи жадібний вибір завжди оптимальний і, до того ж, правильно визначає нездійсненність.

Звідси розв'язок: переберемо кількість монет по . Для кожного значення від до \min(\lfloor s/50 \rfloor,\; c_{50}) обчислимо залишок r = s - 50j і наберемо його жадібно монетами , , у межах наявних кількостей. Якщо залишок вдалося покрити повністю, кандидат на відповідь — плюс кількість використаних дрібних монет. Серед усіх кандидатів беремо найменший.

Перед усім цим варто зробити дві швидкі перевірки: якщо не кратне або перевищує загальну суму всіх монет, відповідь одразу .

Кількість ітерацій не перевищує \min(s/50,\; c_{50}) + 1, тобто щонайбільше близько 2 \cdot 10^6 при s < 10^8, а кожна ітерація — це кілька арифметичних дій. Суми сягають 10^8, тому рахуйте у 64-бітному типі.

Виводимо чотири кількості монет і їхню загальну суму; якщо жоден варіант не підійшов — .