NewBanknote
TCO19 SRM 756 · 2019-04-24 · by misof
Problem Statement
In this problem we use the Euro currency. One euro equals 100 cents. All amounts in this problem will be in cents to avoid dealing with non-integer numbers.
Euro coins have the following denominations: 1, 2, 5, 10, 20, 50, 100, and 200 cents. Euro banknotes have the following denominations: 500, 1000, 2000, 5000, 10000, 20000, and 50000 cents.
There are rumors that the European Committee will soon introduce a new banknote worth newBanknote cents.
In this new monetary system, what will be the smallest number of coins and banknotes needed to pay exactly X cents?
You are given the
Constraints
- newBanknote will be between 1 and 2*10^9, inclusive.
- amountsToPay will have between 1 and 50 elements, inclusive.
- Each element of amountsToPay will be between 1 and 2*10^9, inclusive.
4700
{53, 9400, 9401, 30000}
Returns: {3, 2, 3, 2 }
The new banknote is worth exactly 47 euro. When paying 53 cents, the new banknote is useless. The optimal way uses three coins: 50 + 2 + 1. When paying 94 euro, the optimal solution is to use two new banknotes. When paying 94 euro and 1 cent, the optimal solution is to use two new banknotes and a 1-cent coin. When paying 300 euro, the optimal solution is to use one 100-euro and one 200-euro banknote.
1234
{1233, 1234, 1235}
Returns: {6, 1, 2 }
1000
{1233, 100047}
Returns: {6, 6 }
The new banknote is utterly useless: we already have 10-euro banknotes. Thus, the answer for any amount is the same as when paying using regular Euro denominations only.
1
{2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000 }
Returns: {40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000, 40000 }
1
{1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999 }
Returns: {40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013, 40013 }
Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NewBanknote with a public method vector<int> fewestPieces(int newBanknote, vector<int> amountsToPay) · 123 test cases · 2 s / 256 MB per case