2287Problem C: Ferry Loading V

2287   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 nn 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.
输入样例 复制
5
10.0
50.0
90.0
38.0
7.1
0
输出样例 复制
3 5

说明

1
1
通过提交
时空限制10000ms/128mb
题目来源Waterloo October 2, 2010
评测方式在线评测
题目类型
难        度