Weighing the Grain grain.X
Ever the frugal farmer, FR has acquired a balance-beam style scale
for weighing the grain he gives the cows. This scale works by
reporting if weights placed on its left side match the weight of
the grain on its right side. It is not possible to put weights
anywhere except the left side.
The Ebay auction from which Farmer Ran
bought the scale said, "Several weights included". Unfortunately, the
weights are not the obvious 1, 2, 4, 8, ... or 1, 1, 1, 1, 5, 10,
10, 10, 10, ... sequences. They are, regrettably, not even 'complete'.
That is, the integer sequence of possible weights that _can be constructed_
is missing various integers.
Given a set of W (1 <= W <= 1,000) integer weights, calculate the
first integer greater than or equal to 1 that can not be represented
by some sum of those weights. The answer is guaranteed to fit in
32 signed bits.
PROBLEM NAME: grain
INPUT FORMAT:
* Line 1: A single integer, W
* Lines 2..W+1: Each line specifies a weight present in FJ's set of
weights.
SAMPLE INPUT:
5
1
1
3
4
11
INPUT DETAILS:
Five weights of values: 1, 1, 3, 4 and 11
OUTPUT FORMAT:
* Line 1: The smallest integer that can not be represented by a sum of
the weights
SAMPLE OUTPUT:
10
OUTPUT DETAILS:
1-9 are easy to construct; the first four weights sum to 9; there is no way
to construct 10