1777 . 房屋運動(HOU12)
TopCoder
Tags
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 1
4 2
6 1
Sample Output 1
Sample Input 2
4 0
Sample Output 2
Hints
第一筆範例說明：
兩個員工會在 5 相撞，所以第一個員工的路線是 4-＞5-＞0，需要時間是 6；
第二個員工的路線是 6-＞5-＞9，需要的時間是 5，所以至少要 6 的時間才能讓所有員工都滾出界。
第二筆範例說明：
如果那員工向左滾，路線是 4-＞1，需要的時間是 3；向右滾路線是 4-＞9，需要的時間是 5，
所以至少需要 3 的時間才能讓該員工出界(也就是向左滾)。
(大鈞的示範)
Problem Source
原TIOJ1777 / 99建中校內資訊能力競賽(prob2)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |