A small country is designing its coins. Shop tills give change with a simple rule: always hand over the largest coin that still fits, then repeat on what is left. For some coin systems this rule always uses the fewest coins possible; for others it sometimes wastes coins.
Write first_bad_amount(coins, limit) that returns the smallest amount a with
1 <= a <= limit for which the till's rule uses more coins than the fewest coins that add up to
a. Return -1 if the rule is optimal for every amount up to limit. Every coin can be used any
number of times.
Examples
Input: coins = [1, 3, 4], limit = 10
Output: 6
Explanation: the till pays 6 as 4 + 1 + 1 (three coins), but 3 + 3 uses only two.
Every amount from 1 to 5 is paid optimally.
Input: coins = [1, 5, 10, 25], limit = 100
Output: -1
Input: coins = [1, 10, 25], limit = 100
Output: 30
Explanation: the till pays 25 + 1 + 1 + 1 + 1 + 1 (six coins) instead of 10 + 10 + 10.
Constraints
1 <= len(coins) <= 10, the coins are distinct and1is always one of them1 <= coins[i] <= limit <= 2 * 10**4coinsis not necessarily sorted
Goals
- Simulate a greedy rule and compare it with the true optimum
- Compute the true optimum for every amount with a table
- Find the smallest input on which a greedy rule fails