网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Jan07]找零钱
成绩 | 0 | 开启时间 | 2013年01月18日 星期五 13:25 |
折扣 | 0.8 | 折扣时间 | 2013年01月18日 星期五 13:25 |
允许迟交 | 是 | 关闭时间 | 2013年01月18日 星期五 13:25 |
输入文件 | change.in | 输出文件 | change.out |
Poor Bessie has taken a job in the convenience store located just over the border in Slobbovia. Slobbovians use different coinages than the USA; their coin values change day-by-day!
Help Bessie make optimal change for Slobbovian shoppers. You will need to create C (1 ≤ C ≤ 1000) cents of change using N (1 ≤ N ≤ 10) coins of various values. All test cases will be solvable using the supplied coins.
If 5 coins of values 50, 25, 10, 5, and 1 were available, Bessie would make optimum change (minimal coins) of 93 cents by using 1 x 50, 1 x 25, 1 x 10, 1 x 5, and 3 x 1 coins (a total of 7 coins).
How hard could it be? The final two test cases will be challenging.
Input
- Line 1: Two space-separate integers: C and N
- Lines 2..N + 1: Each line contains a single unique integer that is a coin value that can be used to create change
Output
- Line 1: A single integer that is the minimum number of coins to create C cents
Sample Input
93 5 25 50 10 1 5
Sample Output
7