public
Created

Cash Register Problem

  • Download Gist
gistfile1.md
Markdown

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.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.