TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

46.2% (6/13)

Description

你跟大鈞回到了公司,開始過著平和的生活。

你考量到員工的健康,決定在每天早上把員工集合起來做運動。

而運動的項目就是大鈞的成名絕技:滾來滾去!

可是要如何實行呢?於是你想了一個方法,在第一次運動時跟員工說明:

「為了你們的健康,我決定要讓大鈞教你們滾來滾去 LV1!」

「汪!」在一旁的大鈞附和著。

「恩…還是我來說明好了,為了讓大家都能運動到,你們要先排成一列!」

「汪!」

「然後每個人剛開始可以決定要向左或向右滾,如果撞到了別人,就往另一個方向滾,直到滾出界外就可以去上班了!」

「嗷嗚~!」

想當然爾,每個員工都想越早結束這個愚蠢的運動越好,但是有些員工無法改變自己的習慣,剛開始一定要向左或向右滾。

給你這些員工的資訊,請輸出至少要多久才能讓全部員工結束這愚蠢的運動。

P.S.可以假設所有員工的速度都保持不變,1 單位的時間可以前進 1 單位的距離

Input Format

第一行有三個數字 n,L,R,代表你公司有 n 個員工,
每個員工剛開始的位置都在 L 和 R 之間(最左邊的數字的 L,最右邊的是 R,且 L<R)
滾出去就算到界外可以去工作了。
接下來有 n 行描述每個員工,每行有兩個數字 xi 和 vi,xi代表該員工的位置(L<xi<R),
vi 如果是 1 的話代表該員工剛開始一定是向左滾,
vi 如果是 2的話代表該員工剛開始一定是向右滾,
vi 如果是 0 的話代表該員工剛開始怎麼滾都可以。

PS.你可以假設剛開始每個員工的位置都不同

在10%的測資中 0 < n ≤ 2
在100%的測資中 0 < n ≤ 10000
在40%的測資中 vi 不會有 0
在50%的測資中 0 ≤ L < R ≤ 1000000000
在100%的測資中 0 ≤ L < R ≤ 10100

Output Format

請輸出至少要多久才能讓所有員工做完運動。

Sample Input

Sample Input 1:
2 0 9
4 2
6 1

Sample Input 2:
1 1 9
4 0

Sample Output

Sample Output 1:
6

Sample Output 2:
3

Hints

第一筆範例說明:
兩個員工會在 5 相撞,所以第一個員工的路線是 4->5->0,需要時間是 6;
第二個員工的路線是 6->5->9,需要的時間是 5,所以至少要 6 的時間才能讓所有員工都滾出界。

第二筆範例說明:
如果那員工向左滾,路線是 4->1,需要的時間是 3;向右滾路線是 4->9,需要的時間是 5,
所以至少需要 3 的時間才能讓該員工出界(也就是向左滾)。
(大鈞的示範)

Problem Source

原TIOJ1777 / 99建中校內資訊能力競賽(prob2)

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144
6 10000 65536 262144
7 10000 65536 262144
8 10000 65536 262144
9 10000 65536 262144