1039. When the Greedy Coin Rule Breaks
Given k coin denominations and an amount, print two integers on one
line: how many coins the greedy rule uses, and the true fewest.
The greedy rule takes the largest coin that still fits, repeatedly. If it cannot
reach the amount exactly, report -1 for it. Use -1 for the true answer too
when the amount cannot be made at all.
The point is to make the gap visible. Greedy is correct for the coin systems most people grew up with, which is exactly why it is dangerous: every casual example agrees, and it fails on a set you were not given.
Being able to produce the counterexample is what an interviewer is asking for when they say "why not greedy".
Constraints - `1 ≤ k ≤ 12` - `0 ≤ amount ≤ 10000` - `1 ≤ coin[i] ≤ 10000` - The denominations are distinct.
Input
The first line contains two integers k and amount.
The second line contains k space-separated coin denominations.
Output
Print two integers on one line separated by a single space: the number of coins the greedy rule uses (or -1), then the true fewest (or -1).
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.