Mock CCO '18 Contest 2 Problem 3 - Victor Trains

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.18s
Memory limit: 64M

Problem type

Victor likes trains. Who doesn't?

Victor owns N trains and two rails that are parallel to each other and connected at their ends. The upper rail has trains moving from left to right, the lower rail has trains moving from right to left. When a train reaches an endpoint, it switches to the other rail. Both rails have length M, and when the trains are arranged properly, they are equally separated from each other by a distance of \frac{2M}{N}.

Roger, Victor's arch-nemesis, has disrupted Victor's trains and arranged them haphazardly. Victor wishes to restore the trains so that they are equally separated from each other. To do this, while the trains are moving, he can force any subset of them to stop running for some amount of time or switch them to the opposite rail. Trains move at a rate of one unit per second when not stopped.

Compute the minimum time in seconds needed for Victor to restore balance to his trains!


1 \le N \le 10^5

100 \le M \le 10^8

0 \le x_i \le M.

For at most 50% of full credit, N \le 200.

Input Specification

The first line will contain two integers, M and N.

Each of the next N lines will contain an integer x_i representing the distance from the left endpoint, followed by a character L or R representing the direction that the train is moving in.

Output Specification

Print, on a single line, the minimum amount of time needed for Victor to restore balance. This amount must have an absolute error of at most 10^{-6} when compared with the judge output.

Sample Input

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

Sample Output


Sample Input

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

Sample Output



There are no comments at the moment.