Overview

For each project, determine whether the allocated budget \(A_i\) exceeds the appropriate budget \(B_i\), and find the number of over-budget projects and the total refund amount.

Analysis

This problem is very straightforward — you just need to check each project one by one.

• When \(A_i > B_i\): The project is over budget, so increment the count by 1 and add the refund amount \(A_i - B_i\) to the total.
• When \(A_i \leq B_i\): Do nothing.

For example, suppose there are 3 projects with the following data:

In this case, the number of over-budget projects is 2, and the total refund amount is \(20 + 50 = \) 70.

No special algorithms or data structures are needed — a straightforward approach of checking one by one is sufficient. Since \(N\) is at most \(2 \times 10^5\), processing everything in a single loop poses no issues.

Algorithm

1. Read \(N\).
2. Initialize a counter variable count and a total refund variable total to \(0\).
3. Loop \(N\) times, reading \(A_i, B_i\) for each project:
   • If \(A_i > B_i\), increment count by \(1\) and add \(A_i - B_i\) to total.
4. Output count and total separated by a space.

Complexity

• Time complexity: \(O(N)\) — Each project is checked exactly once.
• Space complexity: \(O(1)\) — Only two variables (a counter and a total) are used; there is no need to store all the data.

Implementation Notes

• The total refund amount can be as large as \(N \times (10^9 - 1) \approx 2 \times 10^{14}\). In C++ and similar languages, you need to use long long, but in Python, integer overflow does not occur, so there is no need to worry about this.

• There is no need to store all the data in an array — processing incrementally while reading the input is sufficient.

  Source Code

N = int(input())
count = 0
total = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A > B:
        count += 1
        total += A - B
print(count, total)

This editorial was generated by claude4.6opus-thinking.