Wesley's Anger Contest 4 Problem 2 - Squirrel Election

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Authors:
Problem types

The squirrel nation is holding a (totally not rigged) election! There are only two candidates in this election: Wesley and Wesley Besley. To reign supreme over the nation, Wesley will do anything to make sure he wins.

The nation is split into N provinces, with the i^{th} province populated by v_i voters. If Wesley earns more than half of the votes in the i^{th} province he is awarded with p_i points, otherwise Besley will automatically get the p_i points. After the voting process, whichever candidate earns the most points in the end wins (ties do not count as a victory). Every squirrel must cast a vote for either of the candidates.

As a very influential candidate, Wesley can force any number of voters to vote for him. Assuming every voter in the nation initially planned to vote for Besley, what is the minimum amount of voters Wesley needs in order to win the election?

For this problem, Python users are recommended to use PyPy over CPython.

Constraints

For this problem, you will NOT be required to pass all the samples to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N \le 5\,000
1 \le v_i \le 10^9
0 \le p_i \le 5\,000
The total sum of p_i is at least 1 and at most 5\,000.

Subtask 1 [20%]

v_i = 1

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains an integer N indicating the number of provinces in the squirrel nation.

The next N lines each contain two integers v_i and p_i separated by a space.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

On a single line, output an integer representing the minimum amount of voters Wesley needs.

Sample Input 1

5
1 5
1 8
1 0
1 1
1 2

Sample Output 1

2

Sample Explanation 1

By forcing a victory with the first two provinces, Wesley can instantly gain 13 points and win the election. Note that 8 points will result in a tie, which will not be enough.

Sample Input 2

6
4 5
9 8
1 0
1 1
1 2
3 4

Sample Output 2

6

Sample Explanation 2

By forcing a victory with the first, fifth, and sixth provinces, Wesley can win the election by threatening 3+1+2 = 6 voters.


Comments


  • 1
    NoOneofConsequence  commented on April 6, 2021, 1:15 p.m.

    I like how in Sample Explanation 2, it's just made clear that Wesley threatens voters.


    • 3
      henrybaolol9  commented on April 6, 2021, 1:50 p.m.

      that's just propaganda. he can win the election because he's a very influential candidate.


      • 3
        crackersamdjam  commented on April 6, 2021, 2:00 p.m.

        The voting doesn't even matter since those who vote decide nothing. It's those who count the vote who decide everything.