Overview

This is a problem of finding the number of students whose average score across submitted answer sheets is below a threshold \(T\). Students who have not submitted any answer sheets are excluded.

Analysis

To solve the problem, we need to manage the following information for each student: - The total score of answer sheets submitted by that student - The number of submitted answer sheets

With this information, we can calculate the average score and compare it with the threshold \(T\). An important point is that students who have not submitted any answer sheets should not be included among the students requiring supplementary lessons.

A naive approach would be to store all answer sheets per student using a 2D array, but since \(N\) and \(M\) can be as large as \(10^5\), this is not appropriate from the perspective of memory usage and computational efficiency. Instead, by managing each student’s total score and number of answer sheets individually, we can process things efficiently.

Algorithm

1. Prepare a data structure (here, a dictionary) to record each student’s total score and number of answer sheets.
2. Process each answer sheet entry one by one:
   • Using the student number \(c_i\) as the key, add \(s_i\) to the total score and increment the answer sheet count by 1.
3. Loop through all students (from 1 to \(N\)), and only for students who have submitted at least one answer sheet, calculate the average score:
   • Average score = total score / number of answer sheets
   • If the average score is less than \(T\), count them as a student requiring supplementary lessons.
4. Output the total number of students requiring supplementary lessons.

Complexity

• Time complexity: \(O(N + M)\)
  • Processing the answer sheet information takes \(O(M)\), and checking the students takes \(O(N)\).
• Space complexity: \(O(N)\)
  • This is for storing information of up to \(N\) students.

Implementation Notes

• Be careful when handling students who have not submitted any answer sheets (keys that do not exist in the dictionary). Students who have not submitted any answer sheets should be skipped.

• Use floating-point division rather than integer division to calculate the average (as per the problem statement’s conditions).

• Since the input data can be large, reading all input at once using sys.stdin.read() improves efficiency.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    T = int(data[2])
    
    scores = {}
    
    index = 3
    for i in range(m):
        c = int(data[index])
        s = int(data[index + 1])
        index += 2
        
        if c not in scores:
            scores[c] = []
        scores[c].append(s)
    
    count = 0
    for student in range(1, n + 1):
        if student in scores:
            total = sum(scores[student])
            average = total / len(scores[student])
            if average < T:
                count += 1
                
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.