TopCoder problem "ConductorWalk" used in East China Round 2 (Division I Level One)



Problem Statement

    

The seats are enumerated from 1 to 100, and the i-th seat is located exactly i meters from the conductor's place. The seats are arranged in a straight line, so there are exactly |i-j| meters between the i-th and j-th seats.

During the trip some passengers may order a tea. The orders are described by int[]s orderSeat and orderTime. The i-th order comes from the passenger at the orderSeat[i]-th seat orderTime[i] seconds after the departure. The orders will be given in chronological order, which means that the (i+1)-th order will always occur later then the i-th.

The conductor can carry at most one cup at once, so to satisfy each order he must walk to the passenger's seat, give him the tea and return back to his own place. He satisfies the orders in chronological order, i.e. in exactly the same order as they are given in the input. The conductor tries to satisfy each order as soon as possible. That is, if he has already satisfied all previous orders by the moment orderTime[i], then he will start satisfying the i-th order exactly at the moment orderTime[i]. Otherwise, he will start satisfying it immediately after all the chronologically earlier orders are satisfied. The conductor walks 1 meter per second and giving tea to a passenger takes no time, so delivering tea to the i-th passenger takes 2 * i seconds.

The passenger seated at seat inspectorSeat is an inspector. Every time the conductor passes by the inspector's seat, the inspector will write down the current time in seconds in his book. Return a int[] containing all times written down by the inspector in increasing order.

 

Definition

    
Class:ConductorWalk
Method:getObserverRecords
Parameters:int[], int[], int
Returns:int[]
Method signature:int[] getObserverRecords(int[] orderSeat, int[] orderTime, int inspectorSeat)
(be sure your method is public)
    
 

Constraints

-orderSeat will contain between 1 and 50 elements, inclusive.
-orderTime and orderSeat will contain the same number of elements.
-Each element of orderSeat will be between 1 and 100, inclusive.
-Each element of orderTime will be between 0 and 10000, inclusive.
-Each element of orderTime will be strictly greater than the previous one.
-inspectorSeat will be between 1 and 100, inclusive.
 

Examples

0)
    
{1, 3}
{5, 105}
2
Returns: {107, 109 }
Two passengers (at seats 1 and 3) request tea during the trip. The sequence of the conductor's actions is given in the following list: 
Time			Event
5			Gets the first order
6                       Delivers the tea to the first passenger
7			Returns back to his place
105			Gets the second order
107			Walks by inspector's seat
108                     Delivers the tea to the second passenger
109                     Walks by inspector's seat on the way back
111			Returns to his place
1)
    
{10, 20, 30}
{0, 5, 10}
1
Returns: {1, 19, 21, 59, 61, 119 }
Time			Event
0			Gets order number 1
1			Walks by inspector
10                      Delivers the tea to the first passenger
19                      Walks by inspector
20			Order number 1 processed, starts processing order number 2
21                      Walks by inspector
40                      Delivers the tea to the second passenger
59                      Walks by inspector
60			Order number 2 processed, starts processing order number 3
61			Walks by inspector
90                      Delivers the tea to the third passenger
119                     Walks by inspector
120			All orders processed
2)
    
{1}
{0}
1
Returns: {1 }
The inspector ordered a tea for himself.
3)
    
{1}
{0}
100
Returns: { }
The inspector is sitting farther away from the conductor than the one passenger who places an order. Therefore, the conductor will never walk by the inspector, and the inspector's book will be empty.
4)
    
{5, 5, 4, 5, 10, 5, 3, 7, 4}
{4, 18, 36, 43, 61, 78, 90, 101, 113}
4
Returns: {8, 10, 22, 24, 40, 48, 50, 65, 77, 85, 87, 105, 111, 119 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9716

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12227&pm=9716

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Simulation