Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Cash Register Problem

Cash Register Problem

Write a program that calculates the optimal number of coins from a set of given denominations to produce a given amount of currency. The correct answer should be the lowest number of total coins given.

Input

The first line:

k d1 d2 ... dk
  • where k in an integer that represents the number of coin denominations to follow on the same line.
  • where d1 ... dk are integers representing the coin denominations in cents.

The second line:

n
  • where n is the number of test cases to follow.

The following n lines:

a
  • where a is an integer that represents the total amount of change to make in cents.

Output

For each test case, output one line:

d1 d2 d3 ...
  • where d1 ... represents one coin of any of the given denominations provided by the input.

Example

Input:

4 1 5 10 25         # four coins: 1, 5, 10 and 25 cents
3                   # three test cases
123                 # 1.23 dollars
7                   # 0.07 dollars
39                  # 0.39 dollars

Output:

25 25 25 25 10 10 1 1 1
5 1 1
25 10 1 1 1 1

Test Cases

http://progg.it/dl/change.zip

Notes

  • Yes, this is a well known weakly NP-hard problem.
  • This means there are a few pseudo-polynomial time solutions to this problem
  • See if you can figure one of them out before you research the problem and its analogs.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.