FLATTEN PROBLEM A solitaire game is played given a row of N piles where each pile contains zero or more chips. See Figure 1. Piles are identified by integers 1 through N. In a move of this game you point to a pile, say p, and specify a number, say m. Then m chips are transferred from the pile p to each of its neighboring piles. See Figure 2 for an example.. Pile p has two neighbors, p1 and p+1 if 1<p<N, and the neighbor 2 if p=1, and the neighbor N1 if p=N. Note that to be able to make such a move the pile p must have at least 2m chips if it has two neighbors, and it must have at least m chips if it has only one neighbor. The object of the game is to "flatten" all piles, that is make them have the same number of chips, by making as small as possible number of moves. In case there is more than one solution you are required to report only one of them.
ASSUMPTIONS
INPUT The input is a text file named flat.inp having two lines.
These integers will be separated with one blank. The i’th number on the second line will be the number of chips in the pile i (1 = i = N )
OUTPUT The output will bemust be the text file named flat.out..
The order of moves on the output must be the same orderthat the moves are performed. So, your first move shall be written to the second line of the output file.
EXAMPLE flat.inp:
flat.out
NOTE ON EVALUATION Your program will be allowed to run 3 seconds. To get full credit, A, for a test case, your number of moves, x, must be less than or equal to the number B, set by the evaluation program. Note that B is not necessarily minimal. In fact, B is chosen for a test case depending on the number of moves made by following a simple strategy with no redundant moves and the average number of chips in the piles. You can obtain partial credit for a test case. The points you get is calculated by rounding to the nearest integer the value obtained by the following formula:
