時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
N 位遊客要搭船渡河，第 i 位遊客的體重為 W_i。每趟船至多搭載 M 位遊客，且乘客總重不能超過 L。只有這 N 位遊客需要渡河，不計船夫重量。請安排各趟乘客，使所有人都能渡河，並計算最少需要的趟數。
輸入格式
第一行為三個正整數 N、M、L，其中 1 ≤ M ≤ N ≤ 17，1 ≤ L ≤ 10^6。
第二行為 N 個以空白分隔的正整數 W_1 至 W_N，且每個 W_i ≤ L。
原題分組限制：30 分：N ≤ 10。40 分：N ≤ 14。30 分：無額外限制。
輸出格式
輸出一個非負整數，表示最少渡河趟數。
範例 1
輸入：
4 2 100
80 70 35 30
輸出：
3
範例 2
輸入：
5 3 80
50 20 30 70 40
輸出：
3
範例 3
輸入：
7 3 120
60 60 50 40 70 30 80
輸出：
4
來源
TOI 2024 年 4 月歷屆題〈搭船渡河〉，依官方 PDF 重新整理。
官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202404/Boat.pdf
標籤：TOI 歷屆
範例測資
範例輸入 1
4 2 100 80 70 35 30
範例輸出 1
3
範例輸入 2
5 3 80 50 20 30 70 40
範例輸出 2
3
範例輸入 3
7 3 120 60 60 50 40 70 30 80
範例輸出 3
4
請先登入後再提交程式碼
討論與題解
載入討論區…