輸入檔: bridge.in / 輸出檔: bridge.out
台大聯誼會舉辦活動,邀請歷屆校友組成海外旅行團。一日,因為交通因素,眾人來到目的地時已經夜深,只有一盞油燈照明,並且要過一條窄橋才能到河對岸的旅館。由於團員老少體能不一,過橋所需的時間不盡相同,走得快的年輕人必須放慢腳步,和同行的長輩一起使用油燈到達彼岸,若是一趟走不完所有的人,則要派一個人把油燈提回來。油燈的燃料有限,若是過橋的先後順序不能妥善安排,可能人還沒走完燈就熄了。請你根據輸入檔的資料,計算出妥善的安排下,最快多少時間所有團員可以安全過橋。
n     輸入檔說明
輸入檔案中有多組測試資料。每組測試資料的第一行有兩個整數n和m,表示總共有n個人過橋,一次最多只能走m個人,且1 £ n, m £ 16。第二行有n個正整數,分別表示每個人過橋所需的時間,且不大於1000。在檔案的最後,以兩個0表示結束。各組測試均有解,即m等於1時,n也會等於1。
n     輸出檔說明
每一組測試資料,都輸出一個整數,表示團員全數過橋所需的最少時間。請每行輸出一組測試資料的答案

範例輸入
1 1
1
3 2
1 2 3
5 2
1 3 6 8 12
0 0
範例輸出
1
6
29
arrow
arrow
    全站熱搜

    vbqa 發表在 痞客邦 留言(2) 人氣()