Overview

For each student, determine whether the average score of their submitted answers is less than the threshold \(T\), and count the number of students requiring supplementary lessons (excluding students who made no submissions).

Analysis

If student \(i\) has \(k\) submissions with scores \(a_1, a_2, \dots, a_k\), the average score is \(\dfrac{a_1+\cdots+a_k}{k}\). We need to determine whether this is less than \(T\) for all students.

The two important points here are:

1. Only the “total score” and “number of submissions” per student are needed to compare the average
   To determine the average, we only need:

   • Total score \(S=\sum a_j\)
   • Number of submissions \(k\) There is no need to store all individual scores.

2. The comparison can be done without using floating-point (decimal) numbers
   \(\dfrac{S}{k} < T\) is equivalent to multiplying both sides by \(k(>0)\):
   \(S < T \cdot k\)
   This allows comparison using only integers, avoiding any precision errors.

Also, note the condition “students who have not submitted anything are excluded,” so students with \(k=0\) should not be considered.

A naive approach of “maintaining a list of scores per student and computing the average” would also run in time since \(M \le 10^5\), but it uses unnecessary memory. Maintaining only the total and count is the simplest and most efficient method.

Algorithm

1. Prepare two arrays of length \(N\) (1-indexed):
   • sums[i]: total score of student \(i\)
   • cnts[i]: number of submissions by student \(i\)
2. For each of the \(M\) submissions, given input \((c, s)\):
   • sums[c] += s
   • cnts[c] += 1
3. For each student \(i=1..N\):
   • If cnts[i] == 0, the student has no submissions, so skip
   • Otherwise, if sums[i] < T * cnts[i], count them as requiring supplementary lessons
4. Output the count.

Example: If student A submitted twice with scores 40 and 60, then \(S=100, k=2\).
Whether the average \(50\) is less than \(T=55\) can be determined by checking \(100 < 55 \times 2 = 110\).

Complexity

• Time complexity: \(O(N+M)\) (\(O(M)\) for aggregation, \(O(N)\) for evaluation)
• Space complexity: \(O(N)\) (arrays for totals and counts)

Implementation Notes

• For average comparison, do not compute \(\dfrac{S}{k}\); always use integer comparison in the form sums[i] < T * cnts[i] (to prevent precision errors).

• Do not forget the condition that students with no submissions (cnts[i] == 0) are not counted as requiring supplementary lessons.

• Since the input can be large, reading it all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    T = next(it)

    sums = [0] * (N + 1)
    cnts = [0] * (N + 1)

    for _ in range(M):
        c = next(it)
        s = next(it)
        sums[c] += s
        cnts[c] += 1

    ans = 0
    for i in range(1, N + 1):
        c = cnts[i]
        if c and sums[i] < T * c:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.