DWITE '09 R6 #4 - Time for Change

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, April 2010, Problem 4

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

In an attempt to make the jobs of cashiers easier (and more accurate!), lets 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 will contain 5 testcases. The first line of the testcase will be the amount needed to be dispensed, an integer 1 \leq m \leq 100. The second line of the testcase will be the number of coin types, an integer 1
\leq n \leq 10. Followed by n lines of coin values, each a unique integer 1 \leq c \leq 100.

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

Note: being greedy will 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 necessary in descending order). It's possible to put together an exact change for 37 in 4 coins -- 25 + 4 + 4 + 4 = 37

Sample Input

66
4
25
10
5
1
37
3
10
25
4

Sample Output

5
4

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments


  • 5
    Jerry_Gu  commented on Nov. 21, 2018, 8:39 a.m.

    It's exactly the same question as dwite08c3p4 but the problem type of that one is Brute Force and this one is Dynamic Programming.