Many thanks to Clive Fraser for creating this puzzle!
The currency for any country will typically include a set of coins with positive integer values. It is clearly important to be able to make any
other positive integer value by adding a number of coins together. If the coin set includes a coin with a value of 1 unit then it is clearly
possible to make any positive integer amount, since this could be done entirely with coins of value 1. If the coin set does not include a
coin with value 1, there will be some positive integer amounts which cannot be reached using the set of coins. If the smallest value coin in
the set has a value of n units, it is obvious that all values less than n cannot be achieved; as well as a number of other values greater
than n.
Consider a simple example where the coin set consists of just two coins, with values of 7 and 9. It is fairly easy to establish that there
are 24 different positive integer amounts which cannot be made using combinations of these two coins. The set of unreachable values is
shown below.
1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 15, 17, 19, 20, 22, 24, 26, 29, 31, 33, 38, 40, 47
Note that all positive integer amounts from 48 onwards can be made from combinations of these two coins. If we add other coin values to
increase the number of coins in the set, we will be able to reduce the number of target values which cannot be reached.
Next consider a coin set consisting of three coins, with values 6, 10 and 16. These three numbers have a common factor of 2. This means
that any combination of these coins must give a total which is divisible by 2. Hence it is not possible to generate any total which is an odd
number; meaning that the number of unreachable values is infinite in this case. To avoid an infinite number of unreachable values, the numbers
in the coin set must not have any common factor (other than 1).
In this problem you will be given a number of different coin sets and are asked, for each one, to find the number of positive integer totals
which are unreachable by making combinations of the coins in the set. The number of coins in the set will be at least 2 and at most 7. It is
guaranteed that the values of the coins in the set will have no common factor (other than 1). The smallest coin in the set will have a value
larger than 1 and all sets will be presented in ascending order of coin value.
Input and output: The first line of the problem will be a single integer N denoting the number of coin sets. Each coin set will be described in 2 lines. The
first line will contain a single integer C for the number of coins in the set. The second line will contain C space-separated integers,
denoting the values for each of the coins in the set. For each coin set you need to calculate the number of positive integer values which
cannot be achieved using combinations of coins in the set. Combine all of the answers, separated by spaces, into a single string.
Example:
input:
3
2
7 9
4
15 26 45 85
7
5967 11539 20898 41371 108728 249172 623788
answer:
24 130 464990