ACM International Programming
South Pacific Problem Set 1999
Problem C Resistance is Facile
An electronic workshop is going to have several boxes of resistors, each containing at least 2,500 resistors of a particular value, different for each box. They may have as few as two boxes or as many as twenty.. They haven't decided what values of resistors to place into each box.
If you combine resistors in series, their values add up. For example, if you combine (in any order) three 500 thousand ohm resistors, two 200 thousand ohm resistors, a 50 thousand ohm resistor, two 20 thousand ohm resistors, a 5 thousand ohm resistor, and two 2 thousand ohm resistors, you get the equivalent of a 1999 thousand ohm resistor. Similarly you could replace the 5 thousand ohm resistor with two 2 thousand ohm resistors and one 1 thousand ohm resistor or one 2 thousand ohm resistor and three 1 thousand ohm resistors or five 1 thousand ohm resistors without changing the total resistance. In order to decide how many boxes to use and what to put in them, the workshop want to find out how easy it will be to make up various values, given a set of boxes. That is, given a number of boxes b, and resistor values 1 <= v1 < v2 < ... < vb in thousands of ohms, they want to know how many different ways there are to make up an n thousand ohm resistance using those values in the boxes, for several values of n.
Input consists of scenarios. Each scenario starts with an integer, b, (2 <= b <= 20). Each scenario ends with a 0 as the only character on a line. The second line in each scenario contains an ascending sequence of b numbers, starting with 1, representing v1 to vb, in that order. This line is followed by a series of lines each conmtaining a single integer representing the values of the resistances we wish to make, in the range 1 to 1999. The list is terminated by the integer 0.
For each value of n in the input output the
number of ways to make up an n thousand ohm resistance, left justified
on a line by itself. The output will not be larger than the value
that your machine can hold in a variable of type unsigned long
1 2 3 4