Distribute idlis Equally

Problem code: EQIDLIS

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((3-1)/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((2-1)/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
Date Added: 18-05-2011
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

can I sort th values to get

aayush123 @ 30 May 2011 01:31 AM
can I sort th values to get result within TL????????

Exceeded time limit ??? god

amzdecoder @ 30 May 2011 01:48 AM
Exceeded time limit ??? god knows why ??

getting TLE, can someone

ankittare @ 12 Jul 2011 09:05 PM
getting TLE, can someone please have a look at my code... http://www.codechef.com/viewsolution/598844

haha .... coolest question

leo90 @ 5 Sep 2011 12:50 AM
haha .... coolest question eva

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions