Overview

Given \(N\) students and \(M\) exam results, the problem asks us to find the number of students who have taken at least one exam and whose average score is below the threshold \(T\).

Analysis

To solve this problem, we need to accurately track the “cumulative total score” and “number of exams taken” for each student.

1. Data Management Since the number of students \(N\) and the number of exam results \(M\) can be as large as \(10^5\), we need to manage each student’s information efficiently. Using the student ID as an index (subscript) and storing the “total score” and “exam count” in arrays (lists) is an efficient approach.

2. Average Comparison and Avoiding Precision Errors The average can be calculated as total score / exam count, but in programming, comparing decimal numbers can introduce errors due to floating-point precision. The condition in this problem is \(\frac{\text{total score}}{\text{exam count}} < T\). Multiplying both sides by exam count (a positive number), we get: $\(\text{total score} < T \times \text{exam count}\)$ By converting to integer multiplication in this way, we can completely eliminate precision errors in the comparison.

3. Excluding Students Who Haven’t Submitted Any Exams The problem statement specifies that “students who have not submitted any answer sheets are not included in the remedial students.” When performing the check, we must verify that the exam count is greater than 0.

Algorithm

We find the solution using the following steps:

1. Initialize arrays total_scores (for cumulative scores) and test_counts (for exam counts) of size \(N+1\) with zeros.
2. Read the \(M\) exam results sequentially and update the corresponding array values for the student with ID \(c_i\).
   • total_scores[c_i] += s_i
   • test_counts[c_i] += 1
3. For each student with ID from \(1\) to \(N\), check whether both of the following conditions are satisfied:
   • test_counts[i] > 0 (has taken at least one exam)
   • total_scores[i] < T * test_counts[i] (average is less than \(T\))
4. Output the total number of students satisfying the conditions.

Complexity

• Time Complexity: \(O(N + M)\)
  • Reading input and aggregating exam results takes \(O(M)\), and checking each student takes \(O(N)\). This runs sufficiently fast for the constraint of \(10^5\).
• Space Complexity: \(O(N)\)
  • The size of the arrays storing each student’s total score and count is proportional to \(N\).

Implementation Notes

• Fast I/O: Since \(M\) can be large, in Python using sys.stdin.read().split() to read all input at once can reduce execution time.

• 1-indexed Handling: Since student IDs start from \(1\), allocating arrays of size \(N+1\) allows us to use student IDs directly as indices, preventing implementation mistakes.

• Comparison Formula: As discussed in the analysis, to avoid decimals, we perform the comparison in the form total score < T * exam count.

  Source Code

import sys

def solve():
    # 全ての入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 基本情報の取得
    N = int(input_data[0])
    M = int(input_data[1])
    T = int(input_data[2])
    
    # 各生徒の合計点と提出数を管理する配列
    # インデックスを生徒の出席番号(1〜N)に合わせるため N+1 のサイズを確保
    total_scores = [0] * (N + 1)
    test_counts = [0] * (N + 1)
    
    # 答案情報の処理
    # 入力データは N, M, T の後、c_i, s_i のペアが続く
    idx = 3
    for _ in range(M):
        c = int(input_data[idx])
        s = int(input_data[idx + 1])
        total_scores[c] += s
        test_counts[c] += 1
        idx += 2
        
    remedial_students = 0
    
    # 各生徒について判定
    for i in range(1, N + 1):
        # 答案を1件以上提出している生徒のみ対象
        if test_counts[i] > 0:
            # 平均値 < T は、合計点 < T * 提出数 と同値（浮動小数点の誤差回避）
            if total_scores[i] < T * test_counts[i]:
                remedial_students += 1
                
    # 結果の出力
    print(remedial_students)

if __name__ == "__main__":
    solve()

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