Overview

This is a problem where, out of \(N\) tests, we want to minimize the number of “failing” tests (those with scores of \(0\) or below). It can be solved by greedily assigning up to \(K\) supplementary lessons, prioritizing tests that require the fewest lessons to avoid failing.

Analysis

First, for tests that already have a score of \(1\) or more, they are not failing, so no supplementary lessons are needed. Let’s consider how many supplementary lessons are needed to save a test with a score of \(0\) or below from failing (i.e., bring it to \(1\) or more).

If we give \(c\) supplementary lessons for a test with score \(H_i\) (\(H_i \le 0\)), the score becomes \(H_i + c \times P\). We need this to be at least \(1\), so: $\(H_i + c \times P \ge 1\)\( \)\(c \times P \ge 1 - H_i\)\( The smallest integer \)c$ satisfying this is the number of supplementary lessons needed to avoid failing that test.

There is an upper limit \(K\) on the total number of supplementary lessons Takahashi can take. To minimize the number of failing tests as much as possible, the optimal strategy is to prioritize assigning lessons to tests that can be saved with fewer supplementary lessons. This approach is known as a Greedy Algorithm.

If we tried to exhaustively search all possible ways to distribute lessons across tests, the number of combinations would be enormous and would exceed the time limit (TLE). However, using this greedy approach, we can find the answer efficiently.

Algorithm

1. Check the score \(H_i\) of each test. Only for tests where \(H_i \le 0\) (currently failing), calculate the number of supplementary lessons needed to avoid failing and add it to a list.
2. Sort the computed list of “required supplementary lessons” in ascending order (smallest first).
3. Set the initial number of failing tests to the length of the list (total number of currently failing tests).
4. Iterate through the sorted list from the beginning, subtracting the required number of lessons from the remaining lessons \(K\):
   • If \(K\) is greater than or equal to the required number, decrease \(K\) and reduce the number of failing tests by \(1\).
   • If \(K\) is insufficient, no more failing tests can be saved, so break out of the loop.
5. Output the final number of failing tests.

Complexity

• Time complexity: \(O(N \log N)\) Checking each test takes \(O(N)\), sorting the list of required supplementary lessons takes \(O(N \log N)\), and scanning the list takes \(O(N)\). Therefore, the overall time complexity is \(O(N \log N)\). This is sufficiently fast for the constraint \(N \le 2 \times 10^5\).
• Space complexity: \(O(N)\) The list storing the required number of supplementary lessons has at most \(N\) elements, so it uses \(O(N)\) memory.

Implementation Notes

• Calculating the required number of supplementary lessons: Python’s floor division // is convenient here. When h <= 0, using (P - h) // P allows us to accurately compute the “minimum number of lessons to reach at least \(1\) point” as an integer, without worrying about floating-point precision errors.

  • Example: When \(P=5, H_i=-4\), \((5 - (-4)) // 5 = 9 // 5 = 1\) lesson.
  • Example: When \(P=5, H_i=-5\), \((5 - (-5)) // 5 = 10 // 5 = 2\) lessons.

• Fast input: By using sys.stdin.read().split(), input data can be read quickly even for large amounts of data. This is an effective technique in competitive programming when \(N\) is large.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    P = int(input_data[2])
    
    req_k = []
    for i in range(3, 3 + N):
        h = int(input_data[i])
        if h <= 0:
            req_k.append((P - h) // P)
            
    req_k.sort()
    
    ans = len(req_k)
    for req in req_k:
        if K >= req:
            K -= req
            ans -= 1
        else:
            break
            
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.