Baltic OI '09 P3 - Subway Signaling Error

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types
Baltic Olympiad in Informatics: 2009 Day 1, Problem 3

The subway in Stockholm consists of several subway lines. In this problem, we will consider one line in particular and the problems that quite often happen on it when there's been a "signaling error".

A subway line can be seen as two parallel rails connected at the endpoints. In the upper rail, the trains are going from right to left and in the lower rail, the trains are going from left to right. When a train reaches an endpoint of a rail, it switches to the opposite rail and changes direction. This switch is instantaneous and takes no time.

During normal traffic, the traffic flow is continuous and the trains are moving at a constant speed (1 length unit per time unit). The trains are evenly distributed; that is, at any given position on a rail, the trains will appear periodically. We will assume that the time it takes for a train to stop and pick up passengers is negligible.

Now, because of signaling errors, the trains have been randomly distributed along the line. Your job as the traffic manager is to, as fast as possible, ensure that the trains will be evenly distributed along the line again. Write a program that, given the current train positions, calculates how fast this can be achieved. You are allowed to order the trains to temporarily stop, and/or change direction anywhere along the line. If a train changes direction, it will move from one rail to the other.

Both rails have a length of 100. In the upper example the trains are positioned at 5 (direction right), 35 (left), 46 (left), 75 (left) and 85 (right). One way to make the trains evenly distributed is for the train at position 46 to travel one unit to the left and then change direction. This takes one time unit. However, this is not the optimal solution; see sample input 1 below.

Input Specification

The first line in the input contains two integers separated by a single space, the length m of the subway rails, and the number n of trains on the line. Then follows n lines each describing the current position of a train. This will be given as an integer x_i and a direction (L for left, R for right), separated by a single space.

Output Specification

Output a single line containing the shortest time it takes to make the trains evenly distributed. Your program should have an absolute precision error of at most 10^{-6}.

Sample Input 1

100 5
5 R
35 L
46 L
75 L
85 R

Sample Output 1


Sample Input 2

100 8
9 L
15 R
41 L
33 L
81 R
33 R
100 L
97 R

Sample Output 2



100 \le m \le 100 \: 000 \: 000

1 \le n \le 100 \: 000

0 \le x_i \le m


For test cases worth 50% of the total score, n \le 200.


There are no comments at the moment.