d119. 有獎徵答:換零錢
標籤 : DP
通過比率 : 737人/826人 ( 89% ) [非即時]
評分方式:
Tolerant

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

內容

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

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

有獎徵答內容:

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

 

(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
20

共9種(不包含10 10)

所以輸出9。

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
23692 alan8656 (阿伯) d119
解題影片
985 2020-12-09 18:16