Overview

Takahashi wants to take at most \(K\) supplementary lessons to minimize the number of failing tests (scores of \(0\) or below). Each supplementary lesson can increase the score of any chosen test by \(P\).

Analysis

Essence of the Problem

The initial score \(H_i\) for each test is given, and scores can be increased by taking supplementary lessons. The goal is to maximize the number of tests with a positive score (\(> 0\)).

Number of Supplementary Lessons Needed to Avoid Failing

When a test has score \(h\) and it is failing (\(h \leq 0\)), the minimum number of supplementary lessons needed to bring the score to at least \(1\) is: $\( k = \left\lceil \frac{1 - h}{P} \right\rceil \)\( This is the smallest non-negative integer \)k\( such that \)h + k \cdot P \geq 1$.

For example, if \(h = -3\), \(P = 2\): - The required increase is \(1 - (-3) = 4\) - The required number of lessons is \(\lceil 4 / 2 \rceil = 2\)

On the other hand, tests that already have a positive score (\(h > 0\)) do not need any supplementary lessons.

Optimal Solution via Greedy Approach

Since the number of supplementary lessons is limited, it is optimal to prioritize saving the failing tests that require the fewest lessons. This allows us to save as many tests as possible from failing.

Specifically, we list the required number of lessons for each failing test, sort them in ascending order, and greedily select them as long as the cumulative total does not exceed \(K\).

Algorithm

1. Check each test score \(H_i\); if \(H_i \leq 0\), the test is failing.
2. For each failing test, compute the number of supplementary lessons needed to make the score positive: \(k = \left\lceil \frac{1 - H_i}{P} \right\rceil\).
3. Collect these lesson counts into a list and sort it in ascending order.
4. Greedily select from the smallest, counting how many can be saved while keeping the total number of lessons used within \(K\).
5. Count the number of failing tests that were saved; the remaining number of failing tests is the answer.

Complexity

• Time complexity: \(O(N \log N)\) (due to sorting)
• Space complexity: \(O(N)\) (array to store the required number of lessons)

Implementation Notes

• Tests with positive scores are unconditionally not failing, so no lessons are needed for them.

• The ceiling function calculation can be implemented as: ceil((1 - h) / P) is equivalent to (1 - h + P - 1) // P.

• Computation can be done efficiently by stopping as soon as the cumulative lesson count exceeds \(K\).

  Source Code

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    P = int(data[2])
    H = list(map(int, data[3:3+N]))
    
    # 赤点回避に必要な補習回数（0以下のものをヒープに）
    required = []
    for h in H:
        if h <= 0:
            # 赤点回避には ceil((1 - h) / P) 回必要
            # つまり (P - h - 1 + P - 1) // P = (P - h - 1)//P + 1 = (P - h + P - 1)//P = (2*P - h - 1)//P
            # 単純に (P - h) // P + (1 if (P - h) % P != 0 else 0) も可能
            # もっと簡単には (-h + P - 1) // P だが、hが負の場合に注意
            # 実際には、h + k*P > 0 なる最小の非負整数kを求めたい
            # h + k*P >= 1 → k*P >= 1 - h → k >= (1 - h)/P
            # 最小の整数kは ceil((1 - h)/P)
            # Pythonのceil(x/y)は (x + y - 1) // y (x,y>0)
            # ただし h が負の場合も考慮して、1 - h > 0 なので問題なし
            k = max(0, (1 - h + P - 1) // P)
            required.append(k)
    
    # 赤点でないものは補習不要
    # 赤点のものについて、必要な補習回数が少ない順にソートして貪欲に処理
    required.sort()
    
    total_used = 0
    count = 0
    for r in required:
        if total_used + r <= K:
            total_used += r
            count += 1
        else:
            break
    
    # 赤点でないものは N - len(required) 個
    not_red = N - len(required)
    # 赤点のうち救えたのは count 個
    red_solved = count
    # 残りの赤点は len(required) - count 個
    red_unsolved = len(required) - count
    
    print(red_unsolved)

if __name__ == "__main__":
    main()

---

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