d119: 有獎徵答

出處

內容：

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

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

有獎徵答內容：

若給你２枚１０元硬幣，要你算出還有多少種排列組合之總數相同（不包含２枚１０元這組）？

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

輸入說明：

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

若該組測試資料只有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

共9種(不包含10 10)

所以輸出9。

範例輸入：

100

200

500

1000

2000

1000 1000

1000 500 200 200 100

範例輸出：

343

3274

135816

3995278

193386179

提示：

當輸入之總金額為50000時，輸出的值小於2⁶²。

出處：

B88000005 (管理：B88000005)

解題策略

找零錢