TAP2014G - Gallantry

no tags 

[ The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.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, each of them is going to pick N/2 players (N is even), the selection process is going to take N/2 turns. On every turn, each of them chooses a different player from the ones who have not been selected yet, and this player is assigned to his/her team. Germán won the coin flip and 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 turn, but not on the first one. In that case, the order of selection of players would be:
[Formula / Figure]
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 more interested on winning the game. He wants to yield his turn as many times as possible so that he can win the game anyway. Gianina also wants to win the game, therefore each time they choose a player they will do it in a way that maximizes their chances of winning.
Input
The first line contains an integer N with the number of players to choose from (with 2 <= N <= 1000, N is 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.

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 P1, P2, ..., PN representing the scores of each player ( Pi  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: 2017-06-02 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: 2016-10-30 07:52:04

fantastic math problem :D

kelaseek: 2015-01-08 06:31:43

before submitting take a look at @fidel's comment

DeViL: 2014-10-08 10:02:45

Last edit: 2014-10-31 06:52:02
Secret Agent: 2014-10-04 20:46:28

@fidel thats not the issue..its passing first 28 judges..can anyone give me some tricky test case?

[reply by cyclops: The judge runs all data sets and only tells you the result afterward. You probably failed on an early test file.]

Last edit: 2014-10-04 22:05:30
Fidel Schaposnik: 2014-10-03 16:15:36

@Secret Agent: no newline at the end of the line ;-)

Secret Agent: 2014-10-03 08:19:29

failing on 28th judge..any suggestions?


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