Problem E
Gas Station
You are a late night attendant at a busy gas station. You
can only go home after all the cars have topped up their fuel
tanks and left the gas station. The gas station you work at has
Cars arriving at the gas station follow strict rules. A car will go to the leftmost open lane that is suitable for its fuel door side. If there are no open lanes, the car will queue up for the suitable lane with the shortest queue. If there are multiple lanes with the shortest queue, the car will queue up in the leftmost one. Once a car has joined a queue, it cannot switch to a different one. After cars leave after refueling and a lane becomes open, the next car in the queue for that lane will go to use a pump.
A lane is open if pump A is available. If pump B is available but pump A is occupied, the lane is not open. When a car goes to an open lane, if both pumps are available, the car will go to pump B, otherwise it will go to pump A. If a car arrives at the same time as some other cars have just finished filling up and left, the new car waits for all other cars in the queues to move to the open pumps (if any) before deciding where to queue. When a car leaves from a pump A, but the pump B ahead of it is occupied, the car is stil able to leave immediately.
You know that Car
Knowing all this, you want to know when you will be able to go home.
![\includegraphics[width=0.5\textwidth ]{diagram.png}](/problems/gasstation/file/statement/en/img-0001.png)
Input
The first line of input contains two space separated
integers,
The next
It is guaranteed that
Output
Output
Sample Input 1 | Sample Output 1 |
---|---|
1 4 1 9 L 2 5 L 3 10 L 4 10 L |
10 7 17 27 |
Sample Input 2 | Sample Output 2 |
---|---|
1 4 1 9 L 2 9 L 3 10 L 4 10 L |
10 11 21 21 |
Sample Input 3 | Sample Output 3 |
---|---|
1 2 8 11 R 9 10 L |
19 19 |
Sample Input 4 | Sample Output 4 |
---|---|
2 10 1 10 R 2 3 R 3 10 R 4 12 R 5 1 R 6 5 R 7 10 R 10 2 R 11 7 R 13 4 R |
11 5 13 16 6 11 21 18 18 22 |