Overview

For each contestant, compute the average score after removing the highest and lowest scores (or the plain average), and determine if they fail to advance by scoring below the threshold. The problem asks for the number of such contestants.

Analysis

In this problem, each contestant is given a list of scores, and the processing method depends on the number of judges \(M\).

• If \(M \leq 2\), the final score is the average of all scores (truncated toward zero).
• If \(M \geq 3\), the final score is the average of the remaining scores after removing one maximum and one minimum value (truncated toward zero).

A straightforward approach is to sort the score list each time and remove the maximum and minimum, which is sufficiently fast. Since \(M \leq 100\), sorting takes \(O(M \log M)\), and processing all \(N\) contestants gives \(O(N \cdot M \log M)\), which fits within the constraints.

Additionally, Python’s integer division // makes truncation toward zero easy to implement.

Algorithm

1. For each contestant, perform the following:
   • Obtain the list of scores.
   • If \(M \leq 2\), the final score is the sum of all scores divided by \(M\) (truncated).
   • If \(M \geq 3\), sort the score list and compute the average of the elements excluding both ends (maximum and minimum), truncated.
2. If the final score is less than the threshold \(K\), increment the counter.
3. Output the value of the counter.

Example

For instance, if a contestant’s scores are [10, 20, 30, 40] and \(K = 26\): - After sorting: [10, 20, 30, 40] - Removing both ends: [20, 30] - Average is \((20 + 30) / 2 = 25\) - Since \(25 < 26\), the contestant fails to advance.

Complexity

• Time complexity: \(O(N \cdot M \log M)\)
• Space complexity: \(O(M)\) (for storing each contestant’s score list)

※ Since \(M\) is at most around 100, this runs sufficiently fast.

Implementation Notes

• Use // for integer truncation division.

• Removing both ends after sorting can be easily done with sorted_scores[1:-1].

• Since each contestant’s score list can be processed independently, the memory can be reused to save space (though be mindful of the trade-off with readability).

  Source Code

import math

# 入力の読み込み
N, M, K = map(int, input().split())
scores = []
for _ in range(N):
    row = list(map(int, input().split()))
    scores.append(row)

# 予選落ち人数のカウント
fail_count = 0

for i in range(N):
    score_list = scores[i]
    if M <= 2:
        # M <= 2 の場合、全得点の平均（切り捨て）
        total = sum(score_list)
        avg = total // M
    else:
        # M >= 3 の場合、最高点と最低点を除いた平均（切り捨て）
        sorted_scores = sorted(score_list)
        trimmed_scores = sorted_scores[1:-1]  # 最大と最小を1つずつ除外
        total = sum(trimmed_scores)
        avg = total // len(trimmed_scores)
    
    if avg < K:
        fail_count += 1

# 結果出力
print(fail_count)

This editorial was generated by qwen3-coder-480b.