| About Olympic -> Problems |  |
|
III Olympiad in Informatics 1995/1996
|
|
Task: KUL
|
Author: Krzysztof Diks
|
| III stage contest |
There are n boxes on the circle. The boxes are numbered from 1 to n (1<=N<=1000) in clock wise order. There are balls in the boxes, and the number of all the balls in the boxes is not greater than n.
The balls should be displaced in such a way that in each box there remains no more than one ball. In one move we can shift a ball from one box to one of it's neighboring boxes.
Task
Write a program that:- reads from the text file KUL.IN the number of boxes n and the arrangement of balls in the boxes,
- computes the minimal number of moves necessary to displace the balls in such a way that in each box there remains no more than one ball,
- writes the result in the text file KUL.OUT.
Input
In the first line of the text file KUL.IN there is written one positive integer n - the number of boxes. In each of the following n lines there is written one nonnegative integer. In the i-th of these lines there is written the number of balls in the i-th box.Output
Your program should write in the text file KUL.OUT one nonnegative integer - the number of moves necessary to displace the balls in such a way that in each box there remains no more than one ball.Example
For the input file KUL.IN:12
0
0
2
4
3
1
0
0
0
0
0
1
the correct answer is the output file KUL.OUT:
19
Your program should look for the file KUL.IN in the current directory and produce the output file KUL.OUT in the current directory too. The file containing the source code of your program should have a name KUL.???, whereas you should put three-letter abbreviation of the used programming language name instead of ???. The same program in executable form should be written in file KUL.EXE