BALIFE  Load Balancing
SuperComputer Inc. have built a superfast computer server consisting of N hyperscalar lightningfast processors Beta 007. These processors are numbered from 1 to N and are used to process independent jobs. Every new incoming job is assigned to an arbitrary processor. Sometimes, a processor may be assigned too many jobs while other processors have a relatively light load (or even wait idly). In that case, the whole system undergoes rebalancing.
Rebalancing proceeds in rounds. In each round, every processor can transfer at most one job to each of its neighbors on the bus. Neighbors of the processor i are the processors i1 and i+1 (processors 1 and N have only one neighbor each, 2 and N1 respectively). The goal of rebalancing is to achieve that all processors have the same number of jobs.
Given the number of jobs initially assigned to each processor, you are asked to determine the minimal number of rounds needed to achieve the state when every processor has the same number of jobs, or to determine that such rebalancing is not possible.
Input file specification
The input file consists of several blocks. Each block begins with a line containing a single number N(1<= N <=9000)  the number of processors. N numbers follow, separated by spaces and/or end of line characters. The ith number denotes the number of jobs assigned to the ith processor before rebalancing. There is a blank line after each block. The last block is followed by a single number 1 on a separate line (which should not be processed).
Output file specification
For each block in the input file, output the minimal number of rounds needed to rebalance loads for all the processors. If it is not possible to rebalance jobs so that each processor has the same number of jobs, output 1.
Example
Input file: 3 0 99 3 2 49 50 8 16 17 15 0 20 1 1 2 10 0 0 100 0 0 0 0 0 0 0 1 Output file: 34 1 23 70
hide comments
md_meraj1319:
20191012 17:34:22
AC in one go. 

rsaw409:
20190831 10:06:36
process of input data in python:


wingman__7:
20190604 07:22:13
refer to this link if you want to understand the logic


syed_tanveer:
20190416 09:18:40
@devil_3 try solving it with pen and paper. You'll get it. 

devil_3:
20190110 08:56:37
Can you guys tell me how you come up with the approach of prefix sum array? Actually how you realized that we should use this or by just hit and trial 

anshuman1117:
20180812 05:45:29
Very easy to get AC in one go! Few hints:


mag1x_:
20180622 13:59:42
Prefix Sum of initial array and balanced array :) 

aryan12:
20180523 14:08:17
AC in 3 chances....just because of a silly mistake, putting cin after the condition to break the loop.


techobist:
20180516 21:56:11
"In case it's not clear, a processor in the middle doesn't have to transfer one job to each neighbour. It can choose in each round not to transfer, to transfer to only one neighbour, or to transfer to both neighbours."


egoista_:
20180428 09:24:29
O(n) solution, AC in one go. Just find the prefix sum of the given array and prefix sum of another array which have all the elements as average. Maximum difference between corresponding positions in these two arrays is the answer. 
Added by:  Fudan University Problem Setters 
Date:  20071103 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  IPSC 2002 