DWITE Online Computer Programming Contest

Time for Change

April 2010
Problem 4

This question is a repeat of question 4 from round 3 in the 2008/2009 season of DWITE. Tony’s flights got rescheduled to red-eye ones for the following day, totally messing up his planned work schedule.

In an attempt to make the jobs of cashiers easier (and more accurate!), let’s write a tool that will figure out the least amount of coins necessary to dispense the exact change.

The caveat is that the tool needs to be dynamic and be able to work with foreign currencies.

The input file DATA4.txt will contain 5 sets of input. The first line of the set will be the amount needed to be dispensed, an integer 1 ≤ m ≤ 100. The second line of the set will be the number of coin types, an integer 1 ≤ n ≤ 10. This is followed by n lines of coin values, each a unique integer 1 ≤ c ≤ 100.

The output file OUT4.txt will contain 5 integers, the minimum number of coins required to make exact change for the input set.

Note: Being greedy will only give part marks. A dynamic solution is required to pass all 5 test cases.

Explanation of sample input, second set: There are three coin types: 25, 10, and 4 (note that input is not necessarily in descending order). It’s possible to put together an exact change for 37 in 4 coins: 25 + 4 + 4 + 4 = 37.

Sample Input (first 2 of 5 shown):
66
4
25
10
5
1
37
3
10
25
4
Sample Output (first 2 of 5 shown):
5
4