b595: Special Touring Car Racing
Tags :
Accepted rate : 82人/93人 ( 88% ) [非即時]

最近更新 : 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.

Sample Input #1
190 260 385 540
130 180 230 330 450
Sample Output #1
0 1 3 4
0 3 5
記憶體限制: 64 MB
公開 測資點#0 (100%): 2.0s , <1K
Hint :
spocktsai (囧rz)

ID User Problem Subject Hit Post Date
es611543 (afa)
570 2019-05-11 11:02