TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

44.4% (4/9)

Tags

Description

有一天,某虫到了心儀很久的某顏色生物家。

他發現她出去旅行了,桌上只留著一本筆記本,好奇心作祟讓他翻開了那本筆記本。

發現筆記本如下紀錄著:

4
台北 -> 桃園 開車 160
桃園 -> 香港 渡輪 100 2 0 10
香港 -> 米蘭 渡輪 50 1 40
米蘭 -> 比薩 開車 160

這就表示某顏色生物她旅行計畫中,依序要搭乘的交通工具,每行前兩個地點表示起訖點。

而第一個數字則表示接下來有幾行。

如果後面接"開車"就表示這段路是要自行開車,後面接的數字就是道路長度(km)。

自行開車時她可以自行決定車速,同一個路段需要等速、例如台北到桃園全程得固定一個速度V1,但可以跟米蘭到比薩的車速不一樣。

但是不論何時,車速最大都不能超過80km/hr,不然會不安全。

如果後面接"渡輪"表示這段行程得搭船,下一個數字表示這趟渡輪航程的花費分鐘(min)。

接下來一個數字k表示一個小時會發幾班渡輪。例如 2 0 10 即表示這個地方0時0分,0時10分,1時0分,1時10分...都會有渡輪航駛。

某虫知道某顏色生物會希望抵達目的地的時間最短,但又同時希望自己的最高車速盡量小,

某虫覺得,他如果能算出某顏色生物整個旅行所花的時間(準確到秒)以及她在途中的最高車速,一定可以討得她的芳心,

但是某虫又不會寫程式,他只好來向你求救,希望你能幫忙他。

(p.s.這個行程至少要花 6 hr 30 min ,當 Vmax = 80.00km/hr)

Input Format

一個測資檔含多筆測資(<=50),每筆測資的第一行有一個數字n,表示這筆測資有幾段路程。

當n=0表示檔案結束,不需對此行作處理。

接下來的第2~+n+1行,每行一定是下面兩種格式之一:

1. [城市名] [城市名] road k
  表示這段路是開車,且路長k。

2. [城市名] [城市名] ferry m k t1 t2 ... tk
  表示這段路是搭渡輪,且需花m 分鐘,每個小時有k個發車時間,依小到大是t1...tk (不會重複)。

一些限制:

1 <= n <= 10,000
0 <= ti <= 59

你可以假定所有城市名稱不超過二十個字元且字元集在[a...zA...Z]之內。

Output Format

對每筆測試資料輸出一行,例如
Test Case 1: 00:05:15 80.00

表示第一組測資,總共要花 0小時5分鐘15秒 ,Vmax = 80.00

Vmax請輸出到小數點下兩位。

Sample Input

1
Bygd Bomvei road 7
2
Ferje Overfarten ferry 20 2 5 25
Overfarten Havneby ferry 30 3 10 30 50
5
Begynnelse Brygge road 30
Brygge Bestemmelse ferry 15 4 10 25 40 55
Bestemmelse Veiskillet road 20
Veiskillet Grusvei road 25
Grusvei Slutt ferry 50 1 10
0

Sample Output

Test Case 1: 00:05:15 80.00
Test Case 2: 01:00:00 0.00
Test Case 3: 03:00:00 45.00

Hints

Problem Source

原TIOJ1630 / World Finals - Hawaii - 2001/2002 Ferries
Problem Setter: ATP

Subtasks

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 65536 2
2 1500 65536 65536 3