You live in LOLandia. Its currency is called 'lulz' and comes in the form of coins and paper banknotes. The smallest paper banknote has a nominal value of 500 lulz. There are six types of coins, each with a different nominal value:
- 200 lulz coin
- 100 lulz coin
- 50 lulz coin
- 20 lulz coin
- 10 lulz coin
- 5 lulz coin
You prefer to keep all your pocket money in the most compact form possible. By "compact" I mean that if you have, say, four 20 lulz coins, plus one 10 lulz coin, plus two 5 lulz coins, then you will exchange them for one 100 lulz coin. Or if the total sum of coins that you have exceeds 500 lulz, then you will exchange all/some of them to banknote(s).
One day you discover that you have the most unfortunate compact combination of coins possible. This means the following:
- This combination is already compact, so it can't be improved.
- Out of all possible compact combinations of coins, this one has the largest total number of all coins.
- Out of all possible compact combinations of coins with the largest number of coins, this one holds the smallest total value of the coins.
What is this combination? You need to say how many coins of each type you have, the total number of coins of all types, and their total value in lulz. It's acceptable to have zero coins of particular type.
P.S. You may use your programming skills to find the answer.
P.P.S. You can make 50,20,20,20 more compact by exchanging 50,20,20,20 to 100,10. Yes, we get 10 and 10<20, but it doesn't matter, what matters is that we got 100, and you exchanged some coins for a higher nominal value. If you can reduce the number of coins by exchanging them, then said combination is not compact.