回分類題庫
d175: 2010 程式達人 F - 過河問題
出處:

Difficulity : 2
Accepted : 30 Times | Submit :109 Times | Clicks : 1667
Accepted : 22 Users | Submit : 27 Users | Accepted rate : 81%
Time Limit :3000 ms | Memory Limit : 64000 KBytes
題目加入時間 : 2010-05-16 19:32

Content :

在一個天氣晴朗的好日子,財哥帶著他的四位工讀生們外出越野健行。在行程快要結束時,由於數天前被『力』使用魔神普蘭勒產生出的颱風所夾帶的大雨,造成他們原本要渡過的醉夢溪溪水暴漲,變成了滾滾黃流,而且此時天色已晚,已經沒有足夠的時候讓他們回頭了。因事前沒有預料到這個狀況,他們身上只有兩件救生衣。為了安全起見,在討論過後決定一定要在有穿著救生衣的狀況下才可以過河。

由於救生衣只有兩件,一次最多只能兩人過河,在平安過河後再請其中一人將救生衣送回,照著這個方法依次的讓大家可以平安的渡過河到對岸。

但因天色已晚,所以必需要以最快的速度過這條河才行,而這五人依照平時的體能狀況來估算,他們過河所需的時間分別為4分鐘、1分鐘、2分鐘、5分鐘、10分鐘。而在過河時,必須要配合走的慢的人的速度,請問一行人過河最快要花22分鐘。不過很不幸的,河岸邊有許多群想要過河的人,很恰巧的每群團體都只有兩件救生衣。身為財哥專業團隊的一員,請幫他們計算出最短過河時間,讓他們能逃離暴漲的溪流。

Input :

輸入的第一列有一個正整數,代表以下有多少組測試資料。每組測試資料的第一列有1個整數n,代表要過河的人數(最多不會超過1000人)。接下來的n列,每列有1個整數,代表這n個人過橋所需的時間(分鐘),這些時間均不會超過100分鐘。

輸入的第一列與第一組測試資料之間,以及各組測試資料之間均有一空白列,請參考範例輸入。

Output :

每組測試資料輸出一行,內容是一個整數,代表這n個人過河所需的最少時間(分鐘)。

Sample Input :

2

5
1
2
4
5
10

4
1
98
99
100

Sample Output :

22
299

Hint :

送出次數: 34 解題率: 0

Author :


  Solve it!   Status Forum (5)

C++
C
JAVA
54093. johnny (8 ms , 226KB)
54091. johnny (8 ms , 236KB)
76813. ji8g2mu (12 ms , 408KB)
49444. CC501 (16 ms , 232KB)
39655. cp100701020 (16 ms , 340KB)
54090. ag100 (12 ms , 248KB)
54089. ag100 (12 ms , 242KB)
54088. ag100 (24 ms , 246KB)
33143. blqc (26 ms , 338KB)
40797. cp100703050 (28 ms , 330KB)
63601. nwgs524513cja (310 ms , 5982KB)
58325. nwgs524513cja (312 ms , 6682KB)
63497. nwgs524513cja (316 ms , 5544KB)
52718. nwgs524513cja (322 ms , 6258KB)

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡