Distribute idlis Equally

All submissions for this problem are available.
Did you know that Chwee kueh, a cuisine of Singapore, means water rice cake ? Its a variety of the most popular South Indian savory cake, only that we call it here idli :). The tastiest idlis are made in Chennai, by none other than our famous chef, Dexter Murugan. Being very popular, he is flown from Marina to Miami, to serve idlis in the opening ceremony of icpc world finals ( which is happening right now ! ).
There are N students and they are initially served with some idlis. Some of them are angry because they got less idlis than some other. Dexter decides to redistribute the idlis so they all get equal number of idlis finally. He recollects his father's code, "Son, if you ever want to redistribute idlis, follow this method. While there are two persons with unequal number of idlis, repeat the following step. Select two persons A and B, A having the maximum and B having the minimum number of idlis, currently. If there are multiple ways to select A (similarly B), select any one randomly. Let A and B have P and Q number of idlis respectively and R = ceil( ( P  Q ) / 2 ), Transfer R idlis from A to B."
Given the initial number of idlis served to each student, find the number of times Dexter has to repeat the above step. If he can not distribute idlis equally by following the above method, print 1.
Notes
 ceil(x) is the smallest integer that is not less than x.
Input
First line contains an integer T ( number of test cases, around 20 ). T cases follows. Each case starts with an integer N ( 1 <= N <= 3000 ). Next line contains an array A of N integers separated by spaces, the initial number of idlis served ( 0 <= A[i] <= N )
Output
For each case, output the number of times Dexter has to repeat the given step to distribute idlis equally or 1 if its not possible.
Example
Input: 3 4 1 2 2 3 2 1 2 7 1 2 3 4 5 6 7 Output: 1 1 3
Explanation:
Case 1 : { 1, 2, 2, 3}. Maximum 3, Minimum 1. R = ceil((31)/2) = 1. Transfer 1 idli from person having 3 idlis to the person having 1 idli. Each of them has 2 idlis now, so just 1 step is enough.
Case 2 : {1,2} R = ceil((21)/2) = 1. {1,2} > {2,1} > {1,2} .... they can never get equal idlis :(
Case 3 : Sorted arrays, in the order encountered {1, 2, 3, 4, 5, 6, 7} > {2, 3, 4, 4, 4, 5, 6} > {3, 4, 4, 4, 4, 4, 5} > {4, 4, 4, 4, 4, 4, 4}
NoteThere are multiple test sets, and the judge shows the sum of the time taken over all test sets of your submission, if Accepted. Time limit on each test set is 3 sec
Author:  flying_ant 
Tester:  masked_zorro 
Editorial  http://discuss.codechef.com/problems/EQIDLIS 
Tags  cook10 easy flying_ant 
Date Added:  18052011 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions