Problem C: Ferry Loading V

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.

For each test case, output a single line giving the numbers of the vehicles that should be directed to the starboard lane. Assume that the other vehicles will be directed to the port lane. The total weight of vehicles on the port side should not differ from that on the starboard side by more than 2%. If there are many solutions, any one will do. There will always be a solution; indeed, there will always be a solution that balances within 1%, but you aren't required to find it.

Sample Input

Possible Output for Sample Input

3 5

Gordon V. Cormack

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.