Rated Contest 1 P5 - Starred

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

It's been a long day, and Max is on the bus headed home. He decides to check his email, and in his starred inbox he finds a puzzle newsletter he is subscribed to. He reads:

Consider a single-file, L meter-long hallway. There are N students in the hallway currently, each facing either left or right. Each student walks at the same speed of S meters per second. Of course, with the hallway being single-file, students are bound to run into each other. In this particular hallway, however, when two students facing opposite directions bump into each other, they both immediately turn around, continuing to walk at the same speed in the opposite direction.

Max pictures a scenario like this, and continues reading,

How long would it take for all the students to exit the hall?

Given students exit the hall when they reach either end of the L meter-length hallway, can you help Max solve this strange scenario?

Constraints

All P_i are distinct.

Subtask 1 [50%]

1 \le P_i < L \le 100

1 \le N \le 5

S = 1

Subtask 2 [50%]

1 \le P_i < L \le 10^9

1 \le N \le 10^5

1 \le S \le L

Input Specification

The first line of input contains three integers: L, N, and S.

The next N lines each contain an integer P_i, representing how far, in meters, the i-th student is from the left-most end of the hallway, and either L (for left) or R (for right), the direction they're facing.

Output Specification

Output one number, the time, in seconds, it takes for all students to exit the hall. Answers within 10^{-6} seconds will be deemed correct.

Sample Input

10 3 2
3 R
7 L
8 R

Sample Output

3.5

Sample Explanation

The first and second students bump into each other 5 meters from the left-most end of the hallway, after 1 second.

The third student exits the hallway after 1 second.

The first and second students then each exit the hallway 2.5 seconds after bumping into each other.


Comments

There are no comments at the moment.