The Codefather

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 2.5s

Memory limit: 16M

Author:

SourSpinach

Problem type

The computer science mafia, headed of course by the Codefather, have control of the points spreadsheet. The Codefather has the power to transfer points from one person to another, disguising these transactions under the Bets column of the spreadsheet.

The Codefather's daughter is getting married, and he wants to give a gift to his future son-in-law, who happens to be taking Grade $12$ ~12~ Enriched CompSci. Since only the person with the most points can get $99\%$ ~99\%~ in this course, the Codefather wants to ensure that his future son-in-law will have strictly more points than anyone else by performing a number of point transfers. However, he's a cautious man (in his business, you have to be), so he follows the following rules:

None of the transfers will involve his future son-in-law.
For each pair of people, he will only perform up to one point transfer, though each transfer can involve any number of points.
A student cannot both give and receive points.
After all the transfers are completed, no students can have a negative amount of points.

There are $N$ ~N~ $(1 \le N \le 5\,000)$ ~(1 \le N \le 5\,000)~ students in this course, each with a unique student number from $1$ ~1~ to $N$ ~N~, inclusive. Student $i$ ~i~ starts off with $P_i$ ~P_i~ $(1 \le P_i \le 1\,000\,000)$ ~(1 \le P_i \le 1\,000\,000)~ points. The Codefather's son-in-law is student $1$ ~1~.

Though the Codefather is a powerful man, he's still wary of the authorities, and wants to remain as inconspicuous as possible. Therefore, he wants to minimize the largest transfers he makes, while still ensuring that his future son-in-law will get $99\%$ ~99\%~ (though with some blackmail, this'll go up to $100\%$ ~100\%~ anyway).

Input Specification

Line $1$ ~1~: The integer $N$ ~N~.
The next $N$ ~N~ lines: Line $i+1$ ~i+1~ contains the integer $P_i$ ~P_i~.

Output Specification

If it's possible for the Codefather to observe the rules and give his future son-in-law more points than anyone else, minimize the largest point transfer he must make and output it.
Otherwise, output impossible.

Sample Input

Sample Output

Explanation

The son-in-law only has $500$ ~500~ points, so the Codefather must make student $3$ ~3~ lose at least $401$ ~401~. However, the other students must also stay strictly below $500$ ~500~. His best strategy is to transfer $199$ ~199~ points from student $3$ ~3~ to student $2$ ~2~, and $202$ ~202~ points from student $3$ ~3~ to student $4$ ~4~. This will result in the following point distribution:

Student $1$ ~1~: $500$ ~500~
Student $2$ ~2~: $499$ ~499~
Student $3$ ~3~: $499$ ~499~
Student $4$ ~4~: $302$ ~302~

Comments

-4

andrewtam commented on Nov. 9, 2020, 8:31 p.m.

Shouldn't the answer for the sample input be 201? Transfer 1 point from S2 to S4, transfer 200 points from S3 to S1, transfer 201 points from S3 to s4.

0

Pookmeister commented on Nov. 9, 2020, 11:33 p.m.

That breaks the first rule - None of the transfers will involve his future son-in-law.

0

andrewtam commented on Nov. 9, 2020, 11:56 p.m.

Sorry, that was actually a typo. I meant to say: transfer 1 point from S2 to S4, transfer 200 points from S3 to S2, transfer 201 points from S3 to s4.

1

chika commented on Nov. 10, 2020, 12:44 a.m.

The statement has been edited to include a clarification that was present on WCIPEG but not on DMOJ. The clarification adds a constraint that makes this sequence of events invalid.