b511. 換銅板 - 高中生程式解題系統

內容

輸入不同面值的銅板，然後輸入一個金額，將全部可能的找零方式列出。譬如有 3 種銅板面值分別是 1元、5 元、10 元，假設要湊出 17 元，如果把找零方法表示成 "(1 元個數,5 元個數,10 元個數)"，總共會有下列幾種方法

(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)

排列順序的規則: 例如 (7,0,1) 先於 (12,1,0) 因為 7 比 12 小；而 (7,0,1) 和 (7,2,0) 的順序，因為第一個數目 7 和 7 相等，這時候就要比第二個數目，而由於 0 小於 2 所以 (7,0,1) 先於 (7,2,0)。

輸入說明

輸入有三行
第一行一個數字 N 代表有幾種不同面值的銅板 (N <= 5)
第二行就是 N 個整數，表示 N 種對應的銅板面值
第三行一個數字是要需要找零的金額

銅板面值和金額都是不超過100的正整數。（補充 by liouzhou_101）

輸出說明

列出每一種找零方法，用括號框住每個銅板的數量，數量之間用逗號隔開，每一種找零方法後面要換行。不同的找零方法的排列順序要依照題目的規定。

範例輸入 #1

3
1 5 10 
17

範例輸出 #1

(2,1,1) 
(2,3,0)
(7,0,1)
(7,2,0) 
(12,1,0)
(17,0,0)

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (50%): 1.0s , <1K
公開測資點#1 (50%): 1.0s , <1K

提示：

Q: 幣值的大小固定是從小排到大嗎?

題目的意思就是，不管你是輸入 1 5 10，還是輸入 5 1 10，或者是 10 1 5 等等..

排列順序都是從第一個幣值開始往後累加

例:

5 1

10

輸出

(0,10)

(1,5)

(2,0)

標籤:

一維陣列排序

出處:

清華 MOOCs 2014 程式設計導論期末考 [管理者： spocktsai (囧rz) ]