There's a payment machine for laundry in my building which does a few frustrating things. The ones relevant to this challenge are:
- It doesn't make change. So if you pay over the amount then you are not getting that over-payment back.
- It doesn't accept coins smaller than 20c. Meaning the only coins it accepts are 20c, 50c, 1€ and 2€ (1€=100c).
- The price of running one machine is 2.30€
The third item doesn't seem immediately frustrating, however if we take a look at all the ways to make 2.30€ we can see an issue:
You may notice that in order to pay 2.30€ you must have at least a 50c coin and four 20c coins. There's no way to substitute other coins in, if you show up and you don't have that combination of coins (plus extra coins to cover the remainder) you are going to have to overpay.
I'm very suspicious that the designers of the machine set the price this way just to make it look reasonable but force over-payment. I think most people end up paying 2.50€ because it's simpler or because their pocket change doesn't meet the stringent requirements to pay exactly 2.30€
To illustrate this hypothesis I have created a strictness index. To measure it you take all the ways you can make a particular price using the available coin set and for each coin type find the option that uses the least of that coin, record the number of that coin used and sum them all up.
If we use the example above, the strictness index is 0 + 0 + 1 + 4 = 5. In fact there is no possible price with a worse strictness index for this set of coins. 5 is the limit.
Not all prices have a strictness index, for example 1.97€ can't be made with the coins above so this procedure doesn't make sense. We just ignore these values, we only care about prices that are possible to make with the given coins.
In this challenge you will take a set of positive integers representing coin values and calculate the maximum strictness index a price can have in this coin system.
The input set will always contain at least 2 values, there will never be duplicates and you may assume it is in strictly ascending or descending order.
This is code-golf so the goal is to minimize the size of your source code as measured in bytes.
2 5 10 20 -> 5 2 3 -> 3 2 3 5 -> 2 1 8 -> 7