LuLu在家無聊看電視,突然轉到一台有獎徵答,CallIn進去答對者可以得到大筆金額,
但答錯了又浪費打電話的錢,所以LuLu想請你寫一個程式,幫他拿到大筆金額。
有獎徵答內容:
若給你2枚10元硬幣,要你算出還有多少種排列組合之總數相同(不包含2枚10元這組)?
(2/2 9:00 加強測試資料、重新整理題目內容)
若該組測試資料只有0,請不要對此輸出任何數字。
(每行的總金額不會超過50000,且數字可為1,5,10,20,50,100,200,500,1000,2000)
範例:
給了10,10,所以要算出總數為20的所有組合總數(不包含10,10)。
對每一組測試資料輸出有多少種用"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。
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