Computer geeks! Show off your skills and claim the job of your dreams! RecruitCoders.com

SPOJ Problem Set (classical)

2123. Candy I

Problem code: CANDY

Jennifer is a teacher in the first year of a primary school. She has gone for a trip with her class today. She has taken a packet of candies for each child. Unfortunatelly, the sizes of the packets are not the same.

Jennifer is afraid that each child will want to have the biggest packet of candies and this will lead to quarrels or even fights among children. She wants to avoid this. Therefore, she has decided to open all the packets, count the candies in each packet and move some candies from bigger packets to smaller ones so that each packet will contain the same number of candies. The question is how many candies she has to move.

Input specification

The input file consists of several blocks of data. Each block starts with the number of candy packets N(1<= N <=10000) followed by N integers (each less than 1000) in separate lines, giving the number of candies in each packet. After the last block of data there is the number -1.

Output specification

The output file should contain one line with the smallest number of moves for each block of data. One move consists of taking one candy from a packet and putting it into another one. If it is not possible to have the same number of candies in each packet, output the number -1.

Example

Input file:
5
1
1
1
1
6
2
3
4
-1

Output file:
4
-1

Added by:	[Trichromatic] XilinX
Date:	2007-12-01
Time limit:	1s
Source limit:	50000B
Languages:	All except: C99 strict ERL JS
Resource:	IPSC 1999

hide comments



2012-04-30 01:24:55 Mitch Schwartz @Byron: Read carefully; I was not referring to N, I was referring to the values of the N integers after that. Based on my test (and initial WA), at least one of these values is 1000 in the input data, which contradicts problem description's guarantee that they are strictly less than 1000. Last edit: 2012-04-30 01:45:59
2012-04-29 18:39:45 Byron Drossos @mitch schwartz no it says 10000 not 1000.
2012-04-09 00:11:14 darky1 Damn..python is slow :X
2012-03-16 07:13:03 Shekhar Kumar Plz provide some more typical test cases !!
2011-12-30 14:06:36 Aditya Last edit: 2012-01-07 15:03:24
2011-10-10 09:50:10 pfiesteria Note:One move consists of taking "one candy"(not candies) from a packet and putting it into another one.
2011-04-12 07:39:41 meiji Oh, I didn't look the problem statement very well. This Input/Output Example is interesting. Last edit: 2011-04-12 07:42:30
2010-10-04 19:26:57 paddyHOD quit good problem
2010-09-26 06:01:28 Mitch Schwartz there is a packet with 1000 pieces of candy in it; please update the description where it says "each less than 1000".