PROBLEM STATEMENT
Note that in the following problem statement, all quotes and angle brackets are for clarity
A certain vending machine delves out its goods from a rotating cylinder, which can rotate around
in both clockwise and counter-clockwise directions. The cylinder has a number of shelves on it,
and each shelf is divided into a number of columns. On the front of the machine, there is a panel
of doors that extends the entire height of the column. There is one door for each shelf, which is
the width of one column. When a purchase is made, the user uses two buttons to rotate the
cylinder so their purchase is located at a door. They make their purchase by sliding the
appropriate door open, and removing the item (there can only be one item per column on a
particular shelf). The cylinder can rotate in a complete circle, and so there are always two ways
to get from a particular column to another column.
Because the vending machine company wants to sell the most expensive items possible, and the
machine can only show one column at a time, the machine will always try to put forth the most
expensive column available. The price of a column is calculated by adding up all the prices of
the remaining items in that column. The most expensive column is defined to be the one with the
maximum price. If 5 minutes have elapsed since the last purchase was made, the machine rotates
the cylinder to the most expensive column. If, however, another purchase has been made before the
5 minutes are up, the rotation does not occur, and the 5 minute timer is reset.
Recently, some machines' rotating motors have been failing early, and the company wants to see if
it is because the machines rotate to show their expensive column too often. To determine this,
they have hired you to simulate purchases and see how long the motor is running.
You will be given the prices of all the items in the vending machine in a vector . Each
element of prices will be a single-space separated list of integers, which are the prices (in
cents) of the items. The Nth integer in the Mth element of prices represents the price of the Nth
column in the Mth shelf in the cylinder. You will also be given a vector purchases.
Each element in purchases will be in the format: ",:"
is a 0-based integer which identifies the shelf that the item was purchased from.
is a 0-based integer which identifies the column the item was purchased from. is
an integer which represents the time, in minutes, since the machine was turned on.
In the simulation, the motor needs to run for 1 second in order to rotate to an adjacent column.
When the machine is turned on, column 0 is facing out, and it immediately rotates to the most
expensive column, even if the first purchase is at time 0. The machine also rotates to the most
expensive column at the end of the simulation, after the last purchase. Note that when an item is
purchased, its price is no longer used in calculating the price of the column it is in. When the
machine rotates to the most expensive column, or when a user rotates the cylinder, the rotation is
in the direction which takes the least amount of time. For example, in a 4-column cylinder, if
column 0 is displayed, and the cylinder is rotated to column 3, it can be rotated backwards, which
takes 1 second, versus rotating forwards which takes 3 seconds.
If a user tries to purchase an item that was already purchased, this is an incorrect simulation,
and your method should return -1. Otherwise, your method should return how long the motor was
running, in seconds.
DEFINITION
Class:VendingMachine
Method:motorUse
Parameters:vector , vector
Returns:int
Method signature:int motorUse(vector prices, vector purchases)
NOTES
-When rotating to the most expensive column, if two columns have the same price, rotate to the one
with the lowest column number (see example 0).
-If two purchases are less than 5 minutes apart, the machine does not perform a rotation to the
most expensive column between the purchases. If two purchases are 5 or more minutes apart, the
machine rotates to the most expensive column between the two purchases.
CONSTRAINTS
-prices will have between 1 and 50 elements, inclusive.
-Each element of prices will have between 5 and 50 characters, is a single-space separated list of
integers, and has no leading or trailing spaces.
-Each element of prices will have the same number of integers in it.
-Each element of prices will have at least 3 integers in it.
-Each integer in prices will be between 1 and 10000, inclusive, and will not contain leading 0's.
-purchases will have between 1 and 50 elements, inclusive.
-Each element of purchases will be in the format ",:" (angle brackets and
quotes are for clarity only), where , , and are all integers.
-In each element of purchases, will be between 0 and M - 1, inclusive, where M is the
number of elements in prices.
-In each element of purchases, will be between 0 and N - 1, inclusive, where N is the
number of integers in each element of prices.
-In each element of purchases, will be between 0 and 1000, inclusive.
-In each element of purchases, , , and will not contain extra leading 0's.
-purchases will be sorted in strictly ascending order by . This means that each purchase
must occur later than all previous ones.
EXAMPLES
0)
{"100 100 100"}
{"0,0:0", "0,2:5", "0,1:10"}
Returns: 4
The vending machine has three columns, and only one row. Since all three items are the same
price, they are all the most expensive, and therefore, the lowest numbered column is rotated to.
Since the machine starts out at column 0, no rotation is performed before the first purchase. The
starting configuration is (*'s denote the currently displayed column):
+-----+-----+-----+
| 100 | 100 | 100 |
+*****+-----+-----+
In the first purchase, the customer does not rotate the cylinder because the item he wants is
already displayed. The configuration of the vending machine is now:
+-----+-----+-----+
| 0 | 100 | 100 |
+*****+-----+-----+
Since the next purchase is at least 5 minutes away, the machine performs a rotation to the most
expensive column. Both column 1 and 2 are now 100 apiece, so it rotates to the smallest index of
these, column 1. The fastest way there is to rotate forward 1 column, yielding 1 second of motor
use:
+-----+-----+-----+
| 0 | 100 | 100 |
+-----+*****+-----+
The next customer purchases the item in column 2, which is 1 column away, so add 1 second to the
motor use. Because another 5 minutes passes, the most expensive column is displayed, which is now
column 1. Add 1 more second for the rotation. The configuration is now:
+-----+-----+-----+
| 0 | 100 | 0 |
+-----+*****+-----+
The final customer purchases from column 1, (which is already displayed), and the final most
expensive column is rotated to. Since all columns are the same price again (0), column 0 is
displayed. It takes 1 second to get back there, so add 1 more second.
1)
{"100 200 300 400 500 600"}
{"0,2:0", "0,3:5", "0,1:10", "0,4:15"}
Returns: 17
The most expensive column during this whole example is column 5. Since all purchases are at least
5 minutes apart, the most expensive column is rotated to each time.
Before the purchases start, add 1 second for rotating to column 5.
The first purchase is 3 columns away, so add 3 seconds to get there, and 3 seconds to get back to
column 5
The second purchase is 2 columns away, so add 4 seconds to get there and back.
The third purchase is also 2 columns away, so add 4 more seconds.
The final purchase is only one column away, so add 2 more seconds.
The final configuration is:
+-----+-----+-----+-----+-----+-----+
| 100 | 0 | 0 | 0 | 0 | 600 |
+-----+-----+-----+-----+-----+*****+
2)
{"100 200 300 400 500 600"}
{"0,2:0", "0,3:4", "0,1:8", "0,4:12"}
Returns: 11
This is the same as example 1, except now, the purchases are all less than 5 minutes apart.
3)
{"100 100 100"}
{"0,0:10", "0,0:11"}
Returns: -1
The second purchase is illegal since the item was already purchased
4)
{"100 200 300",
"600 500 400"}
{"0,0:0", "1,1:10", "1,2:20",
"0,1:21", "1,0:22", "0,2:35"}
Returns: 6
A two-row example. The configurations just before each purchase are:
purchase 1:
+-----+-----+-----+
| 100 | 200 | 300 |
+-----+-----+-----+
| 600 | 500 | 400 |
+*****+-----+-----+
purchase 2:
+-----+-----+-----+
| 0 | 200 | 300 |
+-----+-----+-----+
| 600 | 500 | 400 |
+-----+*****+-----+
purchase 3:
+-----+-----+-----+
| 0 | 200 | 300 |
+-----+-----+-----+
| 600 | 0 | 400 |
+-----+-----+*****+
purchase 4:
+-----+-----+-----+
| 0 | 200 | 300 |
+-----+-----+-----+
| 600 | 0 | 0 |
+-----+-----+*****+
purchase 5:
+-----+-----+-----+
| 0 | 0 | 300 |
+-----+-----+-----+
| 600 | 0 | 0 |
+-----+*****+-----+
purchase 6:
+-----+-----+-----+
| 0 | 0 | 300 |
+-----+-----+-----+
| 0 | 0 | 0 |
+-----+-----+*****+
final:
+-----+-----+-----+
| 0 | 0 | 0 |
+-----+-----+-----+
| 0 | 0 | 0 |
+*****+-----+-----+
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.