PROBLEM STATEMENT
Freight Delivery Company uses belt sorters to sort packages for delivery. Belt
sorter consists of a conveyor belt and eight equally spaced diverters. A stream
of packages enters the belt sequentially, and moves by the diverters. Each
package has a destination diverter assigned to it. It takes the belt one second
to travel the distance between two adjacent diverters. Packages are introduced
on the belt at the rate of one package per second. When a package reaches its
diverter, the diverter activates, and pushes the package off the belt. See
http://www.topcoder.com/contest/belt.html.
Implement a class that calculates the diverter activation sequence. For each
second during which any diverter is activated, the diverter activation sequence
lists numbers of all the diverters activated during that second.
DEFINITION
Class name: BeltSorter
Method name: activations
Parameters: int[]
Return type: String[]
Method signature: String[] activations(int[] assignments) (make sure your
method is public)
assignments contains 0 to 50 elements, inclusive, in the range 0 to 8,
inclusive (TopCoder will check that). If the n-th element contains a value
between 1 and 8, inclusive, it means that the package introduced on the belt
during the n-th second is assigned to the diverter with the corresponding
number. Zero values indicate gaps in the queue of packages.
Elements of the return value of activations should be formatted as follows
(quotation marks are included for clarity only)
"time:diverter,diverter,..."
where time (an integer value) is followed by a single colon (':') character,
and a comma-delimited list of diverters. time represents the number of seconds
elapsed between the introduction of the first packaged on the belt and this
activation. The list of diverters represents the diverters that are activated
at the given time. Diverter numbers should be listed in ascending order.
NOTES
* Diverters are numbered sequentially; diverter number 1 is the closest to the
beginning of the belt, and diverter number 8 is the most distant one. Packages
reach the first diverter one second after their introduction on the belt.
* System limits do not allow activating more than four diverters at any given
second. When assignment requires simultaneous activation of more than four
diverters, only the four diverters with the lowest numbers are activated.
Packages assigned to the remaining diverters are allowed to run off the belt.
As soon as a such package runs off the end of the belt (one second after
passing by the diverter 8), the package is placed in the queue of packages that
have not entered the belt. If there are gaps in the queue, place the run-off
package in the gap nearest to the belt. If there are no gaps in the queue,
place the package at the end of the queue. If there is no queue, introduce the
package on the belt immediately. (see examples 2 and 3).
EXAMPLES
1. If assignments={3,2,4}, the sequence of events is as follows:
- Second 0: package assigned to diverter 3 enters the belt
- Second 1: package assigned to diverter 2 enters the belt; the first package
reaches diverter 1
- Second 2: package assigned to diverter 4 enters the belt; the first package
reaches diverter 2, the second package reaches diverter 1
- Second 3: first and second packages reach their assigned diverters; the third
package reaches diverter 1
- Second 4: the third package reaches diverter 2
- Second 5: the third package reaches diverter 3
- Second 6: the third package reaches diverter 4 - its assigned diverter
Your method should return {"3:2,3","6:4"}
2. If assignments={5,4,3,2,1}, the sequence of events is as follows:
- Seconds 0-4: five packages introduced on the belt, one by one
- Second 5: all five packages reach their destinations; only the first four
diverters are activated. Package assigned to diverter 5 is allowed to run off
the belt.
- Second 9: package assigned to diverter 5 reaches the end of the belt. At this
time, the queue is empty, so the package is re-introduced on the belt right away.
- Second 14: package assigned to diverter 5 reaches its destination.
Your method should return {"5:1,2,3,4","14:5"}
3. If assignments={5,4,3,2,1,0,0,0,0,4,3,0,2}, your method should return
{"5:1,2,3,4","13:3,4","14:2","16:5"}. The initial sequence of events is similar
to that of the prior example. However, when the package assigned to diverter 5
reaches the end of the belt, the remaining queue of packages looks like this:
{4,3,0,2}. The package is re-introduced into the closest gap in the queue,
making it look like {4,3,5,2}.