You are going on a long trip. Initially, you stay at hotel 0. Along the way, there are n hotels. The only place you are allowed to stop are at these hotels. The distance from hotel i - 1 to hotel i is ai . You can choose which of the hotels you stop at. You must stop at the final hotel, which is your destination.
You would ideally like to travel 100 kilometers a day. However, this may not be possible. It depends on the spacing of the hotels. There is no limit on the distance you traveled in a day. If you travel x kilometers during a day, the penalty for that day is (x - 100)2 . You want to plan your trip so as to minimize the total penalty -- that is, the sum, over all travel days, of the daily penalty. Write a program to determine the optimal sequence of hotels at which to stop.
The input file contains a set of test data. Each test data consists of two parts. The first part is the number of hotels n . The second part is a sequence of n integers a1, a2,..., an . Each ai is the distance between hotel i - 1 and hotel i . Assume that 0 < ai < 200 . They may be written in many lines. Assume that n < 1000 , and n = 0 signals the end of the test data.
The first line of the output is the minimum penalty p . The second line of the output is the indexes of the hotels to stop at. If the solution is not unique, print the one with fewer stops. If there are more then one solutions with the same number of stops, print the one which is the lexicographically smallest one. For example (1 2 4) < (1 3 4) . Print 30 stops in each line, except the last line which may contain less stops. Print a blank line between datasets.