Overview

Among \(N\) students, we need to find the number of “students requiring supplementary lessons” whose average score on submitted papers is below the threshold \(T\). However, students who have never submitted a paper are excluded.

Analysis

In this problem, we need to aggregate the scores of submitted papers for each student, calculate their average, and make a determination.

A naive approach would be to search through all papers for each student and compute the average, but since both the number of students \(N\) and the number of papers \(M\) can be up to \(10^5\), a brute-force search would be too slow (the time complexity would be \(O(N \times M)\)).

Therefore, it is important to efficiently aggregate the score list for each student while reading the student number and score pairs contained in each paper. In Python, by using collections.defaultdict, a list corresponding to a key is automatically created, allowing additions without existence checks.

Furthermore, since students who have never submitted a paper must be ignored, we should only process students who have submission records.

Finally, we calculate the average from the total and count of each student’s scores, and determine whether it is less than the threshold \(T\).

Algorithm

1. Read the information of each paper and group scores into lists by student number (using defaultdict(list)).
2. For each student (from 1 to \(N\)):
   • Check if they have any submitted papers.
   • If so, calculate the average of their scores.
   • If the average is less than the threshold \(T\), increment the count.
3. Output the final count.

Complexity

• Time complexity: \(O(M + N)\)
  Each paper is processed once, and then each student is scanned once, resulting in linear time.
• Space complexity: \(O(M)\)
  The memory required to store the information of each paper.

Implementation Notes

• Use sys.stdin.read() to read input quickly (since input() may be slow).

• By using defaultdict(list), scores can be appended without errors even if the key does not exist.

• The average comparison is done with floating-point numbers, but division of integers works fine.

• Don’t forget the condition to skip students who have not submitted any papers.

  Source Code

import sys
from collections import defaultdict

input = sys.stdin.read
data = input().split()

N = int(data[0])
M = int(data[1])
T = int(data[2])

scores = defaultdict(list)

index = 3
for _ in range(M):
    c = int(data[index])
    s = int(data[index+1])
    scores[c].append(s)
    index += 2

count = 0
for student in range(1, N+1):
    if student in scores:
        avg = sum(scores[student]) / len(scores[student])
        if avg < T:
            count += 1

print(count)

This editorial was generated by qwen3-coder-480b.