Catamaran Ballast

Time limit1sMemory limit128 MB

Summary

Split the given rock weights between two hulls so the difference of the two sums is as small as possible.

Level: Medium5 of 10
Topics: Dynamic programming, Brute force
Solved: No attempts yet

Problem

In strong winds, a sailboat tends to heel leeward — to tilt away from the wind. Heeling is undesirable for at least two reasons. First, it reduces the effective sail area: the effective height of the sail is multiplied by the cosine of the heeling angle, and less sail area means less speed. Second, if the boat heels far enough that its centre of gravity is no longer above the hull, the boat capsizes.

To fight this, a catamaran splits its hull into two: a port hull and a starboard hull. The extra width reduces the sail's vertical mechanical advantage (less heeling) and raises the heeling angle the boat can survive before capsizing.

Another remedy is ballast — dead weight added to the hulls to counteract heeling. Our skipper has beached her catamaran and gathered some rocks to use as ballast. She wants the load split as evenly as possible between the two hulls, because an uneven load would itself tip the boat.

Given $n$ rocks, split them between the port and starboard hulls and report the smallest possible difference between the total ballast weight carried by the two hulls.

Input

The input contains several test cases. Each test case begins with a line holding an integer $n$ ( $1 < n \le 100$ ), the number of rocks available as ballast. Each of the next $n$ lines holds one integer between $1$ and $100$ inclusive: the weight in kilograms of a rock. A line containing a single $0$ follows the last test case and must not be processed.

Output

For each test case, print a single line with one integer: the minimum possible absolute difference between the total weight of the rocks placed in the port hull and the total weight placed in the starboard hull, taken over every way of dividing the rocks between the two hulls. Every rock must go into exactly one hull.

Examples4

Example 1
Input
```
5
10
50
90
38
7
0
```
Expected output
```
1
```
Example 2
Input
```
2
40
40
0
```
Expected output
```
0
```
Example 3
Input
```
2
5
5
3
1
2
4
0
```
Expected output
```
0
1
```
Example 4
Input
```
3
1
2
3
0
```
Expected output
```
0
```