Problem Statement
Imagine a vending machine that dispenses drinks. To obtain a drink, a customer inserts a number of coins and presses a button corresponding to a particular type of drink the machine dispenses.
If the customer does not insert an amount of money that is at least the price of a drink, pressing a button will do nothing. In this case, the customer will press the coin return button. This causes the machine to dispense exactly the same coins inserted by the customer, who collects his money and leaves.
If, however, the customer inserts an amount of money that is greater than the price of a drink, then the machine must return to the customer the difference in change when it dispenses the drink. In some cases, however, the machine may not have the coins necessary for returning the exact change. When this is the case, the machine will refuse to dispense a drink, and the customer will press the coin return button to receive his coins as before and leave.
If the customer inserts enough money, the machine can dispense change (if any), and the machine has the drink requested, then it will dispense both the drink requested and the exact change (if any).
You are to simulate the life of a vending machine over the course of a day, and calculate how many drinks the machine dispenses. You will be given four parameters: cost, drinkCounts, coinCounts, and events.
The cost of each drink (in cents) will be given by cost. The
parameter drinkCounts is a
The events parameter specifies a sequence of events. Each event is given
as a
When it is possible for the machine to dispense change, there may be multiple combinations of coins available to the machine that add up to the same sum. When this is the case, choose the combination that consists of the most quarters. If multiple choices maximize the number of quarters, choose the combination that has the most dimes. This will always generate a unique solution.
Definition
- Class:
- Vending
- Method:
- getDrinks
- Parameters:
- int, int[], int[], String[]
- Returns:
- int
- Method signature:
- int getDrinks(int cost, int[] drinkCounts, int[] coinCounts, String[] events)
- (be sure your method is public)
Notes
- cost gives the cost of a drink in cents.
- A quarter is worth 25 cents, a dime is worth 10 cents, and a nickel is worth 5 cents.
Constraints
- cost will be between 5 and 200, inclusive, and will be a multiple of 5.
- drinkCounts will have between 1 and 9 elements, inclusive.
- Each element of drinkCounts will be between 0 and 20, inclusive.
- coinCounts will have exactly 3 elements.
- Each element of coinCounts will be between 0 and 20, inclusive.
- events will have between 0 and 50 elements, inclusive.
- Each element of events will be a String of the form "
", where is a non-negative integer in decimal form (possibly with any number of leading zeros). - There will be exactly one space between each
in each event String. - Each of the first three
s in each event will be between 0 and 100, inclusive. - The last
in each event will be less than the number of elements of drinkCounts.
Examples
65
{2, 4, 1}
{0, 0, 0}
{ "2 1 1 2", "2 1 1 2", "3 0 0 1", "3 0 0 1", "0 6 4 1" }
Returns: 3
"2 1 1 2" - The customer has inserted 2 * 25 + 1 * 10 + 1 * 5 = 65 cents, which is exactly the cost of a drink. The customer requests drink 2, which is available. Since no change needs to be returned, the machine can dispense the drink. As a result, drinkCounts is now { 2, 4, 0 } and coinCounts is now { 2, 1, 1 }. "2 1 1 2" - The customer has inserted the proper change, but no more units of drink 2 are available. Therefore the customer's change is returned, and the state of the machine remains unchanged. "3 0 0 1" - The customer has inserted 75 cents, and is due 10 cents in return. The machine currently has a dime available, so it can dispense change, and the drink requested is also in stock. The machine dispenses the drink and the dime, so drinkCounts is now { 2, 3, 0 } and coinCounts is now { 5, 0, 1 }. "3 0 0 1" - Again, the customer is due 10 cents. However, no combination of coins available in the machine after the customer's coins are inserted will yield 10 cents. Therefore the customer's change is returned and no drink is dispensed. The state of the machine remains the same. "0 6 4 0" - The customer has inserted 80 cents, so is due 15 cents in return. Since the customer has inserted some dimes, it is possible for the machine to return the change as a dime and a nickel, and dispense the requested drink. After this event, drinkCounts is { 1, 3, 0 } and coinCounts is { 5, 5, 4 }. Since 3 drinks were dispensed during the day, the method should return 3.
25
{1, 1, 0}
{1, 0, 0}
{ "0 0 5 2", "0 3 0 1" }
Returns: 0
200
{ 10, 10, 10 }
{ 0, 0, 9 }
{ "7 3 0 0", "7 3 0 0", "7 3 0 0", "7 3 0 0", "7 3 0 0", "7 3 0 0", "7 3 0 0", "7 3 0 0", "7 3 0 0", "7 3 0 0" }
Returns: 9
200
{ 10, 10, 10 }
{ 0, 0, 1 }
{ "7 3 0 0", "7 2 1 0", "7 3 0 0" }
Returns: 3
40
{ 10 }
{ 0, 0, 0 }
{ "1 2 0 0", "2 0 0 0" }
Returns: 0
40
{ 10 }
{ 0, 0, 1 }
{ "1 2 0 0", "2 0 0 0" }
Returns: 2
65
{ 10, 10, 10, 10, 10, 10, 10, 10, 10}
{ 0, 0, 0 }
{ "2 1 1 0", "2 1 1 0", "2 1 1 0", "2 1 1 0", "2 1 1 0", "2 1 1 0", "2 1 1 0", "2 1 1 0", "2 1 1 0", "2 1 1 0", "3 0 0 1", "3 0 0 1", "3 0 0 1", "3 0 0 1", "3 0 0 1", "3 0 0 1", "3 0 0 1", "3 0 0 1", "3 0 0 1", "3 0 0 1", "3 0 0 3", "3 0 0 2", "3 0 0 2", "3 0 0 2", "3 0 0 2", "3 0 0 2", "3 0 0 2", "3 0 0 2", "3 0 0 2", "3 0 0 2", "3 0 0 2", "3 0 0 3", "2 1 1 3" }
Returns: 26
5
{ 4 }
{ 0, 0, 0 }
{ "0 0 1 0", "0 0 0 0", "0 1 0 0", "1 0 0 0" }
Returns: 2
5
{ 6 }
{ 0, 0, 0 }
{ "0 0 1 0", "0 1 0 0", "0 0 1 0", "0 1 0 0", "0 0 1 0", "1 0 0 0" }
Returns: 6
55
{ 10 }
{ 0, 0, 0 }
{ "2 0 0 0", "2 0 1 0", "2 0 1 0", "2 1 0 0", "2 1 0 0", "3 0 0 0" }
Returns: 5
45
{10}
{10,10,0}
{"3 0 0 0" }
Returns: 1