d904: 換零錢
標籤 :
通過比率 : 77% (387 人 / 502 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2014-11-01 02:45

內容
可憐的貝茜在Slobbovia邊境的便利商店工作。Slobbovian國的人使用不同與美國不同的幣值,而且幣值隨時在更動!

請你幫助貝茜做出最佳情況硬幣數給Slobbovian顧客。你需要用N(1<=N<=10)種不同的硬幣數提供C(1<=C<=1000)美分給顧客。你可以假設所有的測資都是可以用此N種硬幣提供出來的。

舉例:如果有5種不同的幣值50,25,10,5,1可用,貝茜將找出93美分的最佳情況硬幣數(最少的硬幣),用1個50,1個25,1個10,1個5,3個1的硬幣(共7個硬幣)為最佳硬幣數。

那能有多難呢?最後兩個測資較具有挑戰性。
輸入說明
每筆測資的第1行有兩數字C與N,其中用一個空格隔開 接下來的第2到第N+1行為各種不同的幣值
輸出說明
輸出最佳情況硬幣數
範例輸入
93 5
25
50
10
1
5
範例輸出
7
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
提示 :
標籤:
出處:
USACO2007January Competition [編輯:
B88000005 (喔~~!!XD)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」