Overview

This problem asks us to minimize the number of failing tests (scores of 0 or below) by raising each test’s score through supplementary lessons. You can take at most K supplementary lessons, and each lesson adds P points to any test of your choice.

Analysis

A straightforward approach would be to allocate supplementary lessons to tests that are at risk of failing. However, the number of lessons required to save each test from failing differs. For example, if the current score is \(-5\) and \(P=2\), at least 3 lessons are needed (\(-5 + 2*3 = 1\) point). The key observation is that it is optimal to prioritize saving tests that require fewer supplementary lessons. This allows us to save the maximum number of tests with the limited K lessons available.

Algorithm

1. For each test \(i\), calculate the number of supplementary lessons \(r_i\) needed to save it from failing (i.e., raise the score from 0 or below to 1 or above):
   • If the current score \(H_i \geq 1\), then \(r_i = 0\) (already saved)
   • Otherwise, \(r_i = \lceil (1 - H_i) / P \rceil\) (ceiling division)
2. Sort the list of required lesson counts in ascending order
3. Compute the prefix sums of the sorted list
4. Use binary search to find the maximum index \(m\) such that the prefix sum is at most K
   • This means we can save \(m\) tests
5. The answer is \(n - m\) (the number of tests we couldn’t save = the number of failing tests)

Complexity

• Time complexity: \(O(N \log N)\) (due to sorting and binary search)
• Space complexity: \(O(N)\) (for the list of required lesson counts and the prefix sum array)

Implementation Notes

• When calculating the required number of lessons, the ceiling division must be handled correctly. The code uses the expression (1 - h + P - 1) // P to achieve ceiling division using integer division

• A 0 is prepended to the prefix sum array to simplify index handling

• In the binary search, we search for the maximum number of elements whose prefix sum is at most K, so we use a lower-bound style search rather than an upper bound

  Source Code

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]))
    
    # 各テストを赤点にしないために必要な補習回数を計算
    required = []
    for h in H:
        # 最終スコアを1以上にするためには、h + x * P >= 1 となる最小のxを見つける
        # x >= ceil((1 - h) / P)
        if h >= 1:
            required.append(0)
        else:
            need = (1 - h + P - 1) // P
            required.append(need)
    
    # 必要な補習回数でソート
    required.sort()
    
    # 累積和を計算
    prefix = [0]
    for i in range(n):
        prefix.append(prefix[-1] + required[i])
    
    # 累積和がK以下となる最大のインデックスを二分探索
    left, right = 0, n
    while left < right:
        mid = (left + right + 1) // 2
        if prefix[mid] <= K:
            left = mid
        else:
            right = mid - 1
    
    # 救えるテストの最大数はleft
    # 赤点の最小数はn - left
    print(n - left)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.