ConductorWalk | Topcoder Archive

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

```
{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
```
{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
```
{1}
```
```
{0}
```
```
1
```
```
Returns: {1 }
```
The inspector ordered a tea for himself.
```
{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.

{5, 5, 4, 5, 10, 5, 3, 7, 4}

{4, 18, 36, 43, 61, 78, 90, 101, 113}

Returns: {8, 10, 22, 24, 40, 48, 50, 65, 77, 85, 87, 105, 111, 119 }

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)2024, Topcoder, Inc. All rights reserved.