2015
02-22

Before bridges were common, ferries were used to transport vehicles across rivers. River ferries, unlike their larger cousins, run on a guide line and are powered by the river’s current. Two lanes of vehicles drive onto the ferry from one end, the ferry crosses the river, and the vehicles exit from the other end of the ferry.
The vehicles waiting to board the ferry form a single queue, and the operator directs each vehicle in turn to drive onto the port (left) or starboard (right) lane of the ferry so as to balance the load. Each vehicle in the queue has a different weight, which the operator estimates by inspecting the queue.

Given n vehicles, you are to compute how to divide them between the port and starboard lanes so that the weight of vehicles on each side is nearly equal.

Input contains several test cases. Each test case begins with 1 < n ≤ 100; the number of vehicles to be boarded. Consider the vehicles to be numbered 1 through n. n lines follow; the ith line gives the weight in tonnes of the ith vehicle – a positive real number not greater than 100. A line containing 0 follows the last test case.

Input contains several test cases. Each test case begins with 1 < n ≤ 100; the number of vehicles to be boarded. Consider the vehicles to be numbered 1 through n. n lines follow; the ith line gives the weight in tonnes of the ith vehicle – a positive real number not greater than 100. A line containing 0 follows the last test case.

5
10.0
50.0
90.0
38.0
7.1
0

3 5