主題

ZeroJudge - d119: 有獎徵答:換零錢 解題心得

Not In My Back Yard | 2021-02-13 00:00:01 | 巴幣 0 | 人氣 28

題目連結:


題目大意:
輸入有多筆測試資料,每筆佔一列。每列給定一個數列(假設該數列數字之總和為 T),數字只會有 1 、 5 、 10 、 20 、
50 、 100 、 200 、 500 、 1000 或是 2000 這十種數字(當有一列只有「0」時,代表輸入結束),代表著正整數 T 用這十種數字湊成的一種方法。

試問除了給定的方法以外,還有多少種方法可以使用十種樹字湊出 T ?



範例輸入:
1
5
10
20
50
100
200
500
1000
2000
1000 1000
1000 500 200 200 100
0


範例輸出:
0
1
3
9
56
343
3274
135816
3995278
193386179
193386179
193386179


解題思維:
典型的換零錢問題,參見這題的做法。

對於每一列輸入先求出 T 之值,接著依據上面題目之求法求出 T 的方法數後,因為要剔除給定的那一個方法,所以要減去 1 即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作