Overview

Given \(N\) projects, the task is to identify cases where the current budget \(A_i\) exceeds the appropriate budget \(B_i\) (i.e., \(A_i > B_i\)), and find the “number of such projects” and the “total excess budget amount (sum of \(A_i - B_i\))”.

Analysis

Since each project is independent, we can simply check them one by one in order.

1. Condition Check: For each project, check whether \(A_i > B_i\).

   • If \(A_i > B_i\): The budget is exceeded. Increment the count by 1 and add \(A_i - B_i\) to the total.
   • If \(A_i \leq B_i\): The budget is within limits. Do nothing.

2. Scale of Values:

   • The number of projects \(N\) is at most \(2 \times 10^5\). Therefore, each individual operation must be done in \(O(1)\), keeping the overall time complexity at \(O(N)\).
   • The total refund amount can be as large as \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\). Python handles large integers automatically, but in other languages (such as C++), be careful to use a 64-bit integer type (such as long long).

Algorithm

1. Initialize a variable over_budget_count to count the number of over-budget projects and a variable total_refund to hold the total refund amount, both set to \(0\).
2. For each of the \(N\) input pairs \((A_i, B_i)\), repeat the following process:
   • If \(A_i > B_i\):
     • Add \(1\) to over_budget_count.
     • Add \(A_i - B_i\) to total_refund.
3. Finally, output over_budget_count and total_refund separated by a space.

Complexity

• Time Complexity: \(O(N)\) Since we scan through \(N\) elements once, the processing completes in time proportional to the number of projects.
• Space Complexity: \(O(N)\) In this implementation, we use sys.stdin.read().split() to read all input at once as a list, so memory usage is proportional to the input size. ※ If rewritten to process input line by line, this can be reduced to \(O(1)\).

Implementation Notes

• Fast Input: In Python, when \(N\) is large (\(10^5\) or more), repeatedly calling input() can lead to long execution times. By using sys.stdin.read().split() to read everything at once, or by using sys.stdin.readline, you can avoid I/O bottlenecks.

• Conditional Branching: The condition “no refund is needed when \(A_i \leq B_i\)” is naturally satisfied by simply implementing the logic to only process cases where \(A_i > B_i\).

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを取得し、空白で分割してリスト化する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # プロジェクト数 N
    n = int(input_data[0])
    
    over_budget_count = 0
    total_refund = 0
    
    # 2個ずつ A_i, B_i を取り出して判定する
    for i in range(n):
        a = int(input_data[1 + 2 * i])
        b = int(input_data[2 + 2 * i])
        
        if a > b:
            over_budget_count += 1
            total_refund += a - b
            
    # 結果を出力
    print(f"{over_budget_count} {total_refund}")

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.