2011年9月29日 星期四

11935 - Through the Desert


想像你正要開著吉普車橫越沙漠,沙漠中有許多危險正等著你,你必須與你的吉普車相依為命,雖然你的吉普車可以放置很大的油箱,但是你不知道到底需要多大,你需要計算能成功橫越沙漠所需的最小油箱容量。

\epsfbox{p11935.eps}
旅途上可能發生的事件如下:


Fuel consumption n
表示吉普車每行進100公里耗的油量(公升)為 n (1 <= n <= 30),旅途中的耗油率隨時都可能改變,例如上坡或下坡。


Leak
漏油,你的油箱被尖銳物品劃到而開始緩緩漏油,每道傷痕都會產生每公里一公升的漏油,愈多漏洞漏油的速度愈快。


Gas station
加油站,能幫你把油加滿。


Mechanic
維修站,會幫你把油箱所有漏洞都補起來。


Goal
目的地,終於抵達目的地了,呼~~

Input

輸入會有多組測試資料,每組資料最多有50個事件,每個事件以一個整數(表示與起點的距離)與事件的類別(如上面說明)來表示。

每組測試資料的第一個事件一定是"0 Fuel consumption n",最後一個事件一定是"d Goal",d表示與起點的距離。

所有事件會以與起點的距離由小到大排序,相同距離可能會發生多起事件,請以出現的順序依序處理。

當出現"0 Fuel consumption 0"表示測試資料結束,此筆資料不做輸出。

Output 

請針對每組測試資料輸出保證能順利到達終點所需的最小油箱容量(體積)。請以公升為單位輸出到小數點後三位。

Sample Input 

0 Fuel consumption 10
100 Goal
0 Fuel consumption 5
100 Fuel consumption 30
200 Goal
0 Fuel consumption 20
10 Leak
25 Leak
25 Fuel consumption 30
50 Gas station
70 Mechanic
100 Leak
120 Goal
0 Fuel consumption 0

Sample Output 

10.000
35.000
81.000


原文出處

2 則留言:

  1. 覺得「到達終點所需的最少油量」應該翻成「最小的油箱體積」

    回覆刪除