Overview

Given \(N\) students, the problem asks to find the number of students whose average score across submitted papers is below a threshold \(T\) (students requiring supplementary lessons). Students who have not submitted any papers are excluded.

Analysis

Organizing the Problem

Each paper records “who submitted it (student ID)” and “the score.” Since the same student may submit multiple papers, we need to aggregate scores per student and compute the average.

Thinking Through a Concrete Example

For example, suppose \(N=3, M=5, T=50\) with the following papers:

Paper	Student ID	Score
1	1	40
2	2	80
3	1	30
4	2	60
5	1	20

• Student 1: Total score \(40+30+20=90\), number of papers \(3\), average \(90/3=30.0\) → \(30.0 < 50\) so requires supplementary lessons
• Student 2: Total score \(80+60=140\), number of papers \(2\), average \(140/2=70.0\) → \(70.0 \geq 50\) so no supplementary lessons needed
• Student 3: No papers submitted → excluded

Therefore, the answer is 1.

Is a Naive Approach Sufficient?

We can read each paper one by one, recording “total score” and “number of papers” per student, and then compute the average for all students at the end. This requires a loop over the \(M\) papers and a loop over the students who submitted papers (at most \(N\)), so it runs in \(O(N + M)\). Since \(N, M \leq 10^5\), this is fast enough.

Algorithm

1. Read input: Obtain \(N, M, T\) and the information for \(M\) papers.
2. Aggregate per student: Using a dictionary (defaultdict), record each student’s “total score (total)” and “number of submitted papers (count)”.
3. Count students requiring supplementary lessons: For each student who submitted at least one paper (i.e., students registered in count), if \(\frac{\text{total}}{\text{count}} < T\), count them as requiring supplementary lessons.
4. Output the result.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) to read and aggregate the \(M\) papers, and \(O(N)\) to evaluate each student who submitted papers (at most \(N\) students).
• Space complexity: \(O(N)\)
  • The dictionary storing total scores and paper counts per student holds at most \(O(N)\) entries.

Implementation Notes

• Using defaultdict: By using student IDs as keys with an initial value of \(0\) for both the total and count, there is no need for existence checks, making the code concise.

• Excluding students with no submissions: By iterating only over students registered in the count dictionary, students who have not submitted any papers are naturally excluded. There is no need to loop over all students from \(1\) to \(N\).

• Floating-point comparison: When comparing the average \(\frac{\text{total}}{\text{count}}\) with \(T\), Python’s / operator performs floating-point division. If you prefer integer comparison, you can rearrange it as total[student] < T * count[student]. However, under the constraints of this problem (scores and threshold at most \(100\), number of papers at most \(10^5\)), there is no concern about floating-point errors.

  Source Code

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1

    total = defaultdict(int)
    count = defaultdict(int)

    for _ in range(M):
        c = int(input_data[idx]); idx += 1
        s = int(input_data[idx]); idx += 1
        total[c] += s
        count[c] += 1

    ans = 0
    for student in count:
        if total[student] / count[student] < T:
            ans += 1

    print(ans)

main()

---

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