EQUI - Equilibrium

no tags 

Original statement in spanish at http://www.dc.uba.ar/events/icpc/download/problems/taip2011-problems.pdf

The mean and the median usually confuse the students because of their similar spelling, but they are quite different concepts. In this problem we are going to work with the mean and the median of a set consisting of N pairwise distinct integers, where N is odd. The mean of such set is defined, as usual, as the sum of the numbers divided by N, while the median is the unique element in the set that is greater than (N-1)/2 of its elements, and less than the other (N-1)/2 elements in the set. For instance, if the set is {0, 2, 6, 4, 13}, then the mean is 5 while the median is 4.

We aim to make student's lives easier by generating "balanced" sets, that is, sets consisting of an odd number of pairwise distinct integers where the mean and the median coincide. For example, the set {0, 2, 6, 4, -2} is balanced, since it has N=5 different integers, and the mean and the median are both equal to 2.

The following procedure has been suggested in order to obtain balanced sets. A set with an even number of distinct integers is chosen, and an extra integer distinct from every element in the set is added to it, in such a way that the resulting set is balanced. We want you to check if the given procedure works. Therefore your task is, given N-1 distinct integers, with odd N, count the number of balanced sets that can be formed by following the described procedure.

Input

The input contains several test cases. Each test case is described with two lines. The first line contains a single odd positive integer N that indicates the number of elements the balanced set must have (3 <= N <= 499). The second line contains N-1 distinct integers Z_i that represent the given elements of the set (-1014 <= Z_i <= 1014 for 1 <= i <= N-1). The last line of the input contains the number -1, and should not be processed as a test case.

Output

For each test case, output a single line with an integer representing the total number of different balanced sets that can be obtained by adding an integer to the given set, as explained in the problem description.

Example

Input:

5
0 2 6 4
7
1 2 3 4 5 8
3
-100000000000000 100000000000000
-1

Output:

3
1
3

hide comments
xopxop1: 2017-08-18 13:20:24

Solution to this and many other tasks are here http://xoptutorials.com/index.php/category/spoj/

Abhishek jaiswal: 2016-04-24 22:21:13

my 100 th :)

seshank: 2012-08-09 22:14:06

answers can be 0,1,2,3 only

Last edit: 2012-08-09 22:14:51
rit: 2012-07-21 09:29:23

My code is working correct for all test case but show wrong answer. Any one plzzz help!!!

mehmetin: 2012-05-02 14:44:26

---

Last edit: 2015-09-28 15:04:18
cegprakash: 2011-11-01 13:16:43

could someone tell what are the three balanced sets possible for first test case?
i can see only one possible way :(

albertg: 2011-10-21 13:58:17

Nice problem.


Added by:Pablo Ariel Heiber
Date:2011-10-04
Time limit:1.046s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2011