TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

27.3% (9/33)

Tags

Description

  霍格華茲魔法與巫術學院是所歷史悠久的魔法學校,在校長阿不思•鄧不利多的領導下,這所學校成為邪惡的黑魔王佛地魔唯一懼怕的地方。在霍格華茲裡,每個魔法教授都會開設專門的魔法學科,例如赫瑞司•史拉轟教授的魔藥學、賽佛勒斯•石內卜教授的黑魔法防禦術、米奈娃•麥教授的變形學等等。而最令一年級新生興奮的課程,就屬胡奇夫人的飛行學了!不只是因為騎著掃帚飛行是每個巫師的必備技巧,而且魔法世界中熱門的的魁地奇運動更需要精湛的飛行技術!在這學期的飛行學中,胡奇夫人為了測驗大家的飛行能力,出了這麼一道難題:她要大家兩個人一組,一開始兩人分別在山脈左右兩邊的山腳下,同時沿著山壁飛行,而且兩個人要隨時保持一樣的高度,最後在最高的山峰處會合。如果哪一組先完成,那一組的學院就可以加五十分,而且還有一支全新的光輪 2005 掃帚作為獎勵!

  為了讓新生們更了解測驗怎麼進行,胡奇夫人找來了哈利和榮恩來示範。假設山脈的地形如上圖所示,哈利和榮恩一開始分別站在 A 點和 K 點沿著山壁往上飛行,並一直保持同樣的高度。當榮恩飛到 J 點的時候,哈利剛好在 B 點,這時如果哈利再往上飛,就會和榮恩的高度不一樣,因此在榮恩越過 J 點的山峰往下飛到 I 點時,哈利也只好跟著往回飛到 C 點。接著,榮恩越過了 I 點的山谷再度往上飛,哈利也跟著往上飛到 D 點的山峰,這時就得換榮恩往回飛了。所以當哈利越過 D 點飛到 E 點時,榮恩就要從 H 點往回飛到 G 點。最後,哈利從 E 點飛到 F 點,而榮恩正好從 G 點也飛到 F 點和哈利會合,才完成胡奇夫人的測驗。因此,哈利的飛行路線是 ABCDEF,而榮恩的則是 KJIHGF。

  可是要怎樣才能最快的會合呢?其實騎著掃帚直線飛行的速度是很快的,可是當轉彎時,由於慣性原理(即使是在魔法世界,也還是有物理定律的存在的!),得先減速掉頭才能再加速飛行,所以越過山峰或山谷,還有掉頭往回飛的時候,會花掉較多的時間。因此,只要比較兩組的路線中轉彎的次數,就可以知道哪一組會花掉較少的時間了。例如在哈利和榮恩的路線中,兩人分別在 B, J 轉了一個彎,在 C, I 又轉一個彎,在 D, H 也轉了一個彎,然後在 E, G 再轉一個彎,最後才在 F 點會合,所以我們可以說他們一共花掉了 $4$ 單位的時間。

  現在,如果你知道山脈的地形,你能不能和你的組員規劃出一個最快的方法到達最高的山峰,以獲得那支令人夢寐以求的光輪 2005 呢?

Input Format

  每筆測試資料的第 $1$ 行是一個整數 $n(1 ≤ n ≤ 199)$,表示山峰和山谷的總數。之後的 $n$ 行之中,每行有兩個數字 $d_i\ h_i(1 ≤ d_i ≤ 10000,0 ≤ h_i ≤ 10000)$,依序表示從左到右第 $i$ 個山峰或山谷與山脈最左邊的山腳的距離為 $d_i$, 高度為 $h_i$。第 $n+1$ 行有一個數字 $d_{n+1}$,表示最右邊的山腳與最左邊的山腳的距離。山脈的地形一定是山峰-山谷-山峰-山谷-...-山峰,而且 $d_1 < d_2 < d_3 < \dots < d_{n+1}$。你可以假設只會有一座最高的山峰。當程式讀到測資的 $n=0$ 時,請不要再輸出任何訊息並結束執行此程式。

Output Format

  輸出檔的第 $k$ 行應該包含一個整數,表示在第 $k$ 筆測試資料給定的地形中,飛到最高峰所需的最短時間。如果沒有辦法用胡奇夫人指定的方式飛到最高峰會合,請輸出 「mission impossible」。

Sample Input 1

5
3 6
5 3
7 8
9 2
11 5
13
0

Sample Output 1

4

Hints

Problem Source

原TIOJ1079 / NPSC2005決賽(prob H)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 30000 65536 262144 1