Fewest Coins When Each Divides the Next
A coin system is given as n values in increasing order, where the smallest is 1 and EACH
VALUE DIVIDES THE NEXT. Pay an exact amount using as few coins as possible, with an unlimited
supply of each.
Print the fewest coins needed.
coins 1 5 25, amount 63 -> 7 two 25s, two 5s, three 1s
coins 1 2 4 8, amount 15 -> 4 8 + 4 + 2 + 1
## Why the knapsack is unusable
Problems 486 and 489 solve exactly this with a table over the amount. That table is correct and
here the amount reaches 10^18, so it cannot be built at any speed.
This is the same situation as 593: the recurrence is fine and the constraints have moved the table out of reach. What is different is that the extra PROMISE in the statement buys a completely different algorithm.
## Take as many of the largest as possible
for each coin from largest to smallest:
used += amount / coin
amount = amount % coin
## Why the promise makes it correct
The greedy is NOT correct for coin systems in general. The standard counterexample is
1 3 4 paying 6: greedy takes 4 + 1 + 1 for three coins, and 3 + 3 uses two. Notice that
3 does not divide 4, so that system is outside this problem's promise.
Here is the argument that the promise repairs it. Let the coins be c[0] = 1 < c[1] < ... <
c[n-1], with each dividing the next, and take any optimal solution.
Suppose it uses t coins of value c[i] where t * c[i] >= c[i+1]. Since c[i] divides
c[i+1], let q = c[i+1] / c[i], which is an integer and at least 2. Then q of those coins
can be replaced by a SINGLE c[i+1], using q - 1 fewer coins.
An optimal solution admits no such improvement, so it uses fewer than q coins of each value
below the top, and that is exactly the remainder the greedy leaves. The two agree at every
level, so the greedy is optimal.
That argument is the whole point of the problem. A greedy without one is a guess, and the divisibility is precisely the hypothesis it needs.
## Always solvable
The smallest coin is 1, so every amount can be paid and there is no impossible case. That is
also why no -1 appears in the output.
## Boundaries
An amount of 0 uses no coins. A system of just 1 uses amount coins, which reaches 10^18
and is why the count itself needs 64 bits, not only the amount.
## Cost
Time O(n). Space O(1).