b595: Special Touring Car Racing
標籤 :
通過比率 : 74% (17 人 / 23 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2015-10-06 08:16

內容

Touring car racing is a car racing competition with heavily modified road-going cars. Most of the game is based on speed to determine the winner. A special touring car race to be held, the rules of this game is very special. The contestants need to rely on the wisdom to win the game.

All contestants start on the road at mile post 0. Along the way there are n parking areas, numbered as 1 <= i <= n, at mile posts a1< a2< . . . < an, where each ai is measured from the starting point. The only places the contestants are allowed to stop are at these parking areas, but they can choose which of the parking areas they stop at. The contestants must stop at the final parking area (at distance an), which is the destination.

The cars are specially designed, so that they would ideally drive 200 miles a day. This may not be possible, because of depending on the spacing of the parking areas. If the contestants drive x miles during a day, the penalty for that day is (200 - x)2. Minimum the sum of the daily penalties of contestant is the winner.

Jonathan wants to participate in this touring car race. Can you help him to win the game?

輸入說明

The input contains several test cases. Each test case has two lines. The first line contains the number of parking areas n. Here n <= 30. The second line contains n integers indicating the values of a1, a2, . . . , an. The values of a1, a2, . . . , an would be integers between 1 and 10000.

The last line of input is only one 0 indicating the end of input.

輸出說明

For each test case, output the parking areas at which to stop. The output starts at 0 and shows the parking areas numbers you stop at in order. The output of each test case should be in a separate line.

範例輸入
4
190 260 385 540
5
130 180 230 330 450
0
範例輸出
0 1 3 4
0 3 5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 2.0s , <1K
提示 :
標籤:
出處:
[編輯:
spocktsai (囧rz)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」