d119: 有獎徵答:換零錢
Tags : DP
Accepted rate : 623人/692人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-03-06 23:19

Content

  LuLu在家無聊看電視,突然轉到一台有獎徵答,CallIn進去答對者可以得到大筆金額,

但答錯了又浪費打電話的錢,所以LuLu想請你寫一個程式,幫他拿到大筆金額。

有獎徵答內容:

  若給你2枚10元硬幣,要你算出還有多少種排列組合之總數相同(不包含2枚10元這組)?

 

(2/2 9:00 加強測試資料、重新整理題目內容)

Input
有多組測試資料,每組測試資料佔一行,每行會有m個以空白分開的正整數,

若該組測試資料只有0,請不要對此輸出任何數字。

(每行的總金額不會超過50000,且數字可為1,5,10,20,50,100,200,500,1000,2000)

 

範例:

給了10,10,所以要算出總數為20的所有組合總數(不包含10,10)。

Output

對每一組測試資料輸出有多少種用"1,5,10,20,50,100,200,500,1000,2000"所排列的組合(不包含輸入的組合)。

 

範例:

所有組合總數為20的排法有:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 1 1 1 1 1 1 1 1 1 1
5 5 5 1 1 1 1 1
5 5 5 5
10 1 1 1 1 1 1 1 1 1 1
5 10 1 1 1 1 1
5 5 10
20

共9種(不包含10 10)

所以輸出9。

Sample Input #1
1
5
10
20
50
100
200
500
1000
2000
1000 1000
1000 500 200 200 100
0
Sample Output #1
0
1
3
9
56
343
3274
135816
3995278
193386179
193386179
193386179
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
當輸入之總金額為50000時,輸出的值小於262。
Tags:
DP
出處:
B88000005 [管理者:
B88000005 (喔~~!!XD)
]


ID User Problem Subject Hit Post Date
23692
alan8656 (阿伯)
d119
解題影片
277 2020-12-09 18:16