Overview

For each player, calculate the final score (floor of the average) from the “sum, minimum, and maximum of scores,” and count the number of players below the threshold \(K\).

Analysis

The key point is that the final score calculation differs depending on whether \(M \ge 3\) or \(M \le 2\).

• When \(M \ge 3\): Remove one highest and one lowest score, then take the average
  That is, given the score array \(a_1,\dots,a_M\):
  [ \text{score}=\left\lfloor\frac{\sum a_i - \min(a) - \max(a)}{M-2}\right\rfloor ]
• When \(M \le 2\): Take the average of all scores
  [ \text{score}=\left\lfloor\frac{\sum a_i}{M}\right\rfloor ]

A naive approach of “sorting the scores each time and removing the min and max” would give the correct answer, but costs \(O(M \log M)\) per player. Since \(N\) can be up to \(10^5\), this means sorting \(10^5\) times in total, which tends to be slow in Python including input handling.

Instead, by computing the sum, minimum, and maximum in a single pass without sorting, each player can be processed in \(O(M)\).

Example: When \(M=5\) and the scores are \([10, 7, 9, 3, 8]\)
- Sum \(s=37\), minimum \(mn=3\), maximum \(mx=10\)
- Sum after removal is \(37-3-10=24\), remaining count is \(5-2=3\)
- Final score is \(\left\lfloor 24/3 \right\rfloor = 8\)

Algorithm

1. Read input \(N, M, K\).
2. Prepare a counter for eliminated players: cnt=0.
3. For each player, do the following:
   • If \(M \ge 3\):
     
     • While reading the \(M\) scores, update the sum s, minimum mn, and maximum mx.
     • [ \text{score} = (s - mn - mx) // (M - 2) ]
     • If score < K, then cnt += 1
   • If \(M \le 2\):
     
     • Compute the sum s of the \(M\) scores, and score = s // M
     • If score < K, then cnt += 1
4. Output cnt.

Complexity

• Time complexity: \(O(NM)\) (each of the \(M\) scores per player is examined exactly once)
• Space complexity: \(O(1)\) (only a constant number of variables such as sum, minimum, and maximum per player)

Implementation Notes

• Separate the processing for \(M \ge 3\) and \(M \le 2\): This is essential to avoid division by zero when \(M-2=0\).

• The “floor of the average” can be expressed in Python using integer division //.

• Since \(N\) can be large, input tends to become a bottleneck in Python. The submitted code speeds this up using sys.stdin.buffer.read() and a custom integer parser.

  Source Code

import sys

data = sys.stdin.buffer.read()
n = len(data)
idx = 0

def next_int():
    global idx
    while idx < n and data[idx] <= 32:
        idx += 1
    val = 0
    while idx < n and data[idx] > 32:
        val = val * 10 + (data[idx] - 48)
        idx += 1
    return val

N = next_int()
M = next_int()
K = next_int()

cnt = 0
if M >= 3:
    denom = M - 2
    for _ in range(N):
        s = 0
        mn = 101
        mx = -1
        for _ in range(M):
            x = next_int()
            s += x
            if x < mn:
                mn = x
            if x > mx:
                mx = x
        score = (s - mn - mx) // denom
        if score < K:
            cnt += 1
else:
    for _ in range(N):
        s = 0
        for _ in range(M):
            s += next_int()
        score = s // M
        if score < K:
            cnt += 1

sys.stdout.write(str(cnt))

This editorial was generated by gpt-5.2-high.