Ferry Loading V

Time limit1sMemory limit128 MB

Summary

Given distinct vehicle weights, split them between two lanes so the totals differ as little as possible. Output the minimum difference.

Level: Medium5 of 10
Topics: Dynamic programming, Prefix sum, Math
Solved: No attempts yet

Problem

Vehicles are loaded onto a ferry in two lanes, a port (left) lane and a starboard (right) lane. Every vehicle has a distinct weight, and you want to split them between the two lanes so that the total weight on each lane is as close as possible. Compute the minimum possible difference between the total weight of the two lanes.

Input

The input contains several test cases. Each test case begins with a line containing the number of vehicles $n$ ( $1 < n \le 100$ ). The next $n$ lines each give the weight of one vehicle in tonnes, one per line. Each weight is a positive number not exceeding $100.0$ , given to one digit after the decimal point (that is, in multiples of $0.1$ tonnes). Within a single test case all weights are distinct. A line containing a single $0$ follows the last test case.

Output

For each test case, print on its own line the minimum possible difference between the total weight of the two lanes, in tonnes, with exactly one digit after the decimal point.

Examples2

Example 1
Input
```
5
10.0
50.0
90.0
38.0
7.1
0
```
Expected output
```
0.9
```
Example 2
Input
```
4
1.0
2.0
3.0
4.0
0
```
Expected output
```
0.0
```