TAP2014G  Gallantry
[ The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014problems.pdf ]
Every weekend, Germán and Gianina play a football match with their friends. This Saturday, both German and Gianina are injured, so they will participate in the game as coaches.
To choose the teams they will use the following procedure: of the N friends they have in common, each of them is going to pick N/2 players (N is even), with the selection process taking N/2 turns. On every turn, each of them chooses a different player among the ones who have not been selected yet, and this player is assigned to his/her team. Germán won the initial coin flip so he gets to choose first on every turn. However, to be gallant Germán can let Gianina go first on some turns if he wants so.
For example, if N = 6 there are N/2 = 3 turns. Suppose Germán decides to yield his right to choose first on the second and third turns, but not on the first one. In that case, the order of selection of players would be:
Germán  Gianina  Gianina  Germán  Gianina  Germán
Turn 1 Turn 2 Turn 3
As we all know, football is a sport ruled by logic. Every friend of Germán and Gianina has a score that indicates how well they play. If the sum of scores of Germán's team is strictly greater than the sum of scores of Gianina's team, then Germán's team will win the match. If the sum of scores is the same for both teams, the match ends in a draw. Otherwise, Gianina's team will be the winner.
Germán wants to be gallant, but he is even more interested in winning the game. Therefore, he wants to yield his turn as many times as possible so that he can still win the game anyway. Gianina also wants to win the game, therefore each time they choose a player they will both do it in a way that maximizes their chances of winning.
Input
The first line contains an integer N representing the number of players to choose from (with 2 ≤ N ≤ 1000 and N even). The second line contains N integers P_{1}, P_{2}, ..., P_{N} representing the scores of each player (1 ≤ P_{i} ≤ 1000 for i = 1, 2, ..., N).
Output
Print a line containing a single integer that represents how many times Germán can yield his turn in such a way that his team's victory is guaranteed. If Germán can not ensure a victory, you must print the number 1.
Example 1
Input: 6 7 8 2 10 1 4 Output: 1
Example 2
Input: 6 7 8 2 10 1 3 Output: 2
Example 3
Input: 4 60 95 100 65 Output: 0
Example 4
Input: 10 10 10 10 10 10 10 10 10 10 10 Output: 1
hide comments
jorgenamour:
20170602 03:33:46
Hi, i trying to solve this problem with Python 3.5 and i have the output of the judge: "runtime error (NZEC)". Any suggestion? 

cjycjy:
20161030 07:52:04
fantastic math problem :D 

kelaseek:
20150108 06:31:43
before submitting take a look at @fidel's comment 

DeViL:
20141008 10:02:45
Last edit: 20141031 06:52:02 

Secret Agent:
20141004 20:46:28
@fidel thats not the issue..its passing first 28 judges..can anyone give me some tricky test case?


Fidel Schaposnik:
20141003 16:15:36
@Secret Agent: no newline at the end of the line ;) 

Secret Agent:
20141003 08:19:29
failing on 28th judge..any suggestions?

Added by:  Fidel Schaposnik 
Date:  20140929 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Argentinian Programming Tournament 2014 