Overview

This problem asks you to count and output the number of students in each class whose test scores are at least the passing threshold \(K\).

Analysis

This is a straightforward problem where you simply check each student’s score in each class and count how many satisfy the condition.

Key Observations

1. Each class is independent: There’s no need to share information between classes; we can process each class sequentially
2. Simple condition check: For each student, we just need to determine “Is the score \(\geq K\)?”

Is a Naive Approach Sufficient?

For this problem, checking each student exactly once is sufficient. Looking at the constraints: - The total number of students across all classes: \(\sum_{i=1}^{N} M_i \leq 10^6\)

This means we only need to check at most \(10^6\) students once each, so a naive approach is perfectly adequate.

Concrete Example

Consider the following input example:

3 60
3 55 70 80
2 60 59
4 100 50 60 70

• \(N = 3\) (number of classes), \(K = 60\) (passing threshold)
• Class 1: Scores are 55, 70, 80 → Scores of 60 or above: 70, 80 → 2 students
• Class 2: Scores are 60, 59 → Scores of 60 or above: 60 → 1 student
• Class 3: Scores are 100, 50, 60, 70 → Scores of 60 or above: 100, 60, 70 → 3 students

The output is 2, 1, 3.

Algorithm

1. Read \(N\) (number of classes) and \(K\) (passing threshold) from the first line
2. For each class \(i\) (\(i = 1, 2, \ldots, N\)):
   • Read the number of students \(M_i\) and each student’s score from that line
   • Count the number of students with scores \(\geq K\)
   • Output the count

Complexity

• Time complexity: \(O\left(\sum_{i=1}^{N} M_i\right)\)
  • Proportional to the total number of students, since we check each student once
  • At most \(O(10^6)\)
• Space complexity: \(O\left(\max(M_i) + \text{total input size}\right)\)
  • When processing each class, we store the score list for that class
  • If reading input all at once, memory usage equals the size of the entire input

Implementation Notes

1. Fast input reading: Using sys.stdin.read() to read all input at once allows efficient processing of large amounts of data.

2. Input format considerations: The first value on each line is the number of students \(M_i\), followed by \(M_i\) scores. line[0] is the number of students, and line[1:] is the list of scores.

3. Counting process: In Python, you can concisely count elements satisfying a condition using sum(1 for s in scores if s >= K). This is equivalent to:

   count = 0
   for s in scores:
      if s >= K:
          count += 1
   

   Source Code

import sys

def main():
    input_data = sys.stdin.read().split('\n')
    first_line = input_data[0].split()
    N = int(first_line[0])
    K = int(first_line[1])
    
    for i in range(1, N + 1):
        line = list(map(int, input_data[i].split()))
        M = line[0]
        scores = line[1:M + 1]
        count = sum(1 for s in scores if s >= K)
        print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.