Many places like to have the ability to determine the value of coins simply by weighing them - places like highway toll booths, vending machines, and even banks.
However, coins do not have exact weights, as much as we'd like them to for problems like this. Due to variances in types of metals, corrosion, and general wear and tear on coins, each denomination of coin has a minimum and a maximum weight. Of course, each coin also has an associated value. You will be given the value and the minimum and maximum weights for each denomination, as well as the weight of a number of coins. You must determine what possible values the coins could possess.
For instance, let's say that a penny (worth one unit) has a minimum weight of 19 and a maximum weight of 21. Let's also say that a nickel (worth five units) has a minimum weight of 40 and a maximum of 43. Now let's assume we're given a number of coins whose weight is 105. There could be two nickels weighing 43 each, and a penny weighing 19, for a total value of 11 units. Another possibility is to have 5 pennies weighing 21 each, for a value of 5 units.
Each denomination of coin will be represented by three integers in a String as follows (angle brackets are for clarification only):
"<value> <minimum weight> <maximum weight>"
The return value should be the number of distinct possible values. For instance, if the coins could be worth 1, 2, or 4, the return value would be 3.
|