同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21159_MakingChange

2022-5-16 18:18| 发布者: Hocassian| 查看: 41| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504949489700-Problem List-采集的数据-后羿采集器.html

Pro.ID

21159

Title

Making Change

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21159

AC

Submit

Ratio

21.67%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

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 × 50, 1 × 25, 1 × 10, 1 × 5, and 3 × 1 coins (a total of 7 coins).

How hard could it be? The final two test cases will be challenging.

输入

Multiple test cases, for each case:

* 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

输出

Description

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!

How hard could it be? The final two test cases will be challenging.

Input

Multiple test cases, for each case:

* 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

Source

USACO 2007 January Bronze