ACSU Programming Competition

26 September 1998

Problem 1 - Making Change

Last summer, Cornell astronomer Philip Nicholson, among others, discovered two new moons of Uranus, which have been named Caliban and Sycorax. Even though we just discovered them, they have existed for millennia. There are some people, however, who have known about the moons for quite some time: the residents of Uranus, called the Uranoids. The Uranoids have a very advanced civilization. All of the problems will deal with some aspect of Uranoid life.

Description

The most valuable element on Uranus, of course, is uranium. As a result, it is used as money in the Uranoid society. As it happens, all of the coins are the same size, and thus the same weight. When a Uranoid receives change from a purchase, it is customary to give as few coins as possible, to minimize the weight of the change.

You are to read the values of coins, and an amount of change to be given. You will determine which coins should be used to make change, to minimize the total number of coins. There will always be a coin with value 1. You have an infinite supply of all coins; you don't have to worry about running out.

Incidentally, the Uranoids use the symbol U as we use the symbol $. So, U1 is a coin with a value of one Uranoid dollar.

Input / Output

The first line of input will indicate the number of data sets. This number will be non-negative.

The first line of each data set contains two positive integers; call them m and n. Both are positive. m is the number of coins in the data set. The second line contains m positive integers, in strictly increasing order. These are the coin values. The first coin always has value 1. The next n lines each contain a single positive integer. For each of these integers, call it c, you are to determine how many of each coin are to be given so the total value of all coins is c, and the total number of coins is minimized. The output should be given as described in Sample Output, below.

If there is more than one way to make change while using the minimum number of coins, any answer is acceptable.

There are at most 16 coins in any data set (i.e., m <= 16). You will be asked to determine change for no more than U5000 (i.e., c <= 5000).

Example

Suppose there are 3 coin values, of U1, U4, and U5. To make change for U7, you should use two U1 coins and one U5 coin. To make change for U8, you should use two U4 coins.

Once again, suppose there are 3 coin values, of U1, U2, and U3. There are two ways to make change for U4 using a minimum number of coins: U1 and U3, or two U2. Either answer is acceptable.

Sample

Sample Input

The comments to the right are not part of the actual input. They are included to help you understand the input format.

2                Number of data sets.
3 2              Beginning of first data set. m = 3 and n = 2.
1 4 5            These are the three coin values.
7                Determine how to make change for U7 using the three coins.
8                Determine how to make change for U8.
6 4              Beginning of second data set. m = 6 and n = 4.
1 2 4 8 16 32    These are the six coin values.
9                Determine how to make change for U9 using the six coins.
10               Determine how to make change for U10.
11               Determine how to make change for U11.
4999             Determine how to make change for U4999.

Sample Output

At the beginning of each data set, print a message indicating the data set number. For each amount that you are to determine change for, print out the amount, then print out the n integers, where the first integer is the number of the first coin, the second is the number of the second coin, etc. Follow the format shown below.

The output corresponding to the above input is given below. Once again, the comments to the right are not part of the actual output.

Data set 1:             Beginning of data set 1.
U7 = 2 0 1              U7 = two U1 and one U5
U8 = 0 2 0              U8 = two U4
Data set 2:             Beginning of data set 2.
U9 = 1 0 0 1 0 0        U9 = one U1 and one U8
U10 = 0 1 0 1 0 0       U10 = one U2 and one U8
U11 = 1 1 0 1 0 0       U11 = one U1, one U2, and one U8
U4999 = 1 1 1 0 0 156   U4999 = one U1, one U2, one U4, and 156 U32

Solution

Here is the solution by Daniel Gerstenzang in C++.

Here is the test input:

3
3 4
1 4 5
7
8
4001
4999
6 6
1 2 4 8 16 32
9
10
11
3999
4000
5000
16 11
1 2 3 5 7 11 13 17 23 29 31 37 103 407 999 1001
1
33
67
100
330
670
1000
2000
3000
4000
5000

Here is the correct output:

Data set 1:
U7 = 2 0 1
U8 = 0 2 0
U4001 = 1 0 800
U4999 = 0 1 999
Data set 2:
U9 = 1 0 0 1 0 0
U10 = 0 1 0 1 0 0
U11 = 1 1 0 1 0 0
U3999 = 1 1 1 1 1 124
U4000 = 0 0 0 0 0 125
U5000 = 0 0 0 1 0 156
Data set 3:
U1 = 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
U33 = 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0
U67 = 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
U100 = 1 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0
U330 = 1 0 1 0 0 0 0 1 0 0 0 0 3 0 0 0
U670 = 0 0 1 0 0 0 0 1 0 0 0 1 2 1 0 0
U1000 = 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
U2000 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
U3000 = 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1
U4000 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2
U5000 = 1 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2

Other solutions are possible. Any solution that makes the correct amount of change while using the minimum number of coins was accepted.

Last updated 30 November 1998.

This page is maintained by Adam Florence. If there are any questions or corrections, please e-mail me.