時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
信封最多可貼 S 張郵票。給定多套郵票面額，對每套找出最大連續涵蓋值 C，使 1 到 C 的每個郵資都能以至多 S 張郵票湊出；面額可重複使用。例如面額 1、3，最多 5 張時可連續湊出 1 到 13，但不能湊出 14，所以 C=13。
選出 C 最大的面額套組；若同分，先選面額種類較少者，再從最大面額向下逐一比較，選第一次差異處面額較小者。
輸入格式
每筆先有 S（最多 10），下一個整數 N 表示套組數（最多 10）。接著 N 行，先有該套組的面額種類數，再接由小到大排列的面額；種類數不超過 S，最大面額為 100。以 S = 0 結束。
輸出格式
每筆輸出 max coverage =，接著以寬度 4 靠右輸出 C，再印空白、冒號；各面額依遞增順序以寬度 3 靠右輸出。
範例測資
範例輸入 1
5 2 4 1 4 12 21 4 1 5 12 28 10 2 5 1 7 16 31 88 5 1 15 52 67 99 6 2 3 1 5 8 4 1 5 7 8 0
範例輸出 1
max coverage = 71 : 1 4 12 21 max coverage = 409 : 1 7 16 31 88 max coverage = 48 : 1 5 7 8
請先登入後再提交程式碼
討論與題解
載入討論區…