Problem Statement

John and Brus have an interest in team sports tournaments. They are investigating a soccer tournament that is currently in progress. Soccer is a team sport played between two teams of eleven players using a spherical ball. It is the most popular football variant worldwide, and is widely considered to be the most popular sport in the world.

In this tournament, each game results in either a victory for one team or a draw. If a team wins a game, it gains three points and its opponent gains no points. In case of a draw, each team gains one point. The score of a team is the sum of all the points it has gained from all its games. Each pair of teams can play against each other any number of times.

You are given a int[] points representing the current standings in the tournament. The i-th element of points is the score of the i-th team. You can assume that the points represent a valid state, i.e., intermediate standings that can be achieved in a tournament according to the rules described above.

Each team will play exactly one more game in the tournament, but it is not known what the matchups will be. After the tournament is over, the teams will be ranked by score. 1st place will go to the team with the highest score, 2nd place will go to the team with the second highest score, and so on. If two teams have the same score, the team with the lower number will place higher. For example, if team 0 and team 3 each have the highest score of 100 points, then team 0 will place 1st and team 3 will place 2nd.

John's favorite team is team 0, and he wants it to place as high as possible. Assuming that the remaining games can be scheduled arbitrarily and can end with any possible outcome, return the highest possible place for team 0 at the end of the tournament.

Definition

 Class: TheSoccerDivTwo Method: find Parameters: int[] Returns: int Method signature: int find(int[] points) (be sure your method is public)

Constraints

-points will contain between 2 and 50 elements, inclusive.
-points will contain an even number of elements.
-Each element of points will be between 0 and 1,000,000, inclusive.
-points will represent a valid state.

Examples

0)

 `{4, 7}`
`Returns: 1`
 John's favorite team wins the only game.
1)

 `{4, 7, 7, 7}`
`Returns: 2`
 It's impossible for John's favorite team to be in first place after the remaining games.
2)

 `{5, 9, 11, 9, 10, 9}`
`Returns: 6`
 John's favorite team has too few points here to rise above last place.
3)

 `{2, 1, 3, 7, 6, 5, 3, 4, 2, 6, 5, 1}`
`Returns: 4`

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10690

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13907&pm=10690

Vasyl[alphacom]

Testers:

PabloGilberto , ivan_metelsky , Chmel_Tolstiy

Greedy