d904: 換零錢
Tags :
Accepted rate : 439人/579人 ( 76% ) [非即時]
評分方式:
Tolerant

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

Content
可憐的貝茜在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個硬幣)為最佳硬幣數。

那能有多難呢?最後兩個測資較具有挑戰性。
Input
每筆測資的第1行有兩數字C與N,其中用一個空格隔開 接下來的第2到第N+1行為各種不同的幣值
Output
輸出最佳情況硬幣數
Sample Input
93 5
25
50
10
1
5
Sample Output
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
Hint :
Tags:
出處:
USACO2007January Competition [管理者:
B88000005 (喔~~!!XD)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」