All submissions for this problem are available.
John and Dan 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 match ups 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.
The first line of input file contains a positive integer n, the number of teams. Next line contains n space separated integers points[i] (1<=i<=n) where points[i] represents the score of the ith team in the tournament.
Output a single integer as per the requirements given in the problem statement.
- 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.
Input: 2 4 7 Output: 1
Input: 4 4 7 7 7 Output: 2
|Time Limit:||1 - 1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.