Overview

Given \(N\) quizzes, for quizzes with scores of \(0\) or below (failing), optimally allocate up to \(K\) supplementary lessons (each adding \(P\) points) to minimize the number of failing quizzes.

Analysis

Key Observations

1. Quizzes that are already passing (\(H_i > 0\)) need no action. Supplementary lessons only need to be used for quizzes where \(H_i \leq 0\).

2. The number of supplementary lessons needed to pass each failing quiz is determined. When quiz \(i\) has score \(H_i \leq 0\), we need \(H_i + k \cdot P > 0\). The minimum \(k\) satisfying this is:

\[k = \left\lceil \frac{1 - H_i}{P} \right\rceil\]

For example, if \(H_i = -5\) and \(P = 3\), then \(1 - (-5) = 6\), so \(\lceil 6/3 \rceil = 2\) supplementary lessons are needed. Indeed, \(-5 + 2 \times 3 = 1 > 0\), which is a pass.

1. We should prioritize saving quizzes with the smallest cost. Since the number of supplementary lessons \(K\) is finite, it is optimal to save quizzes in order from those requiring the fewest lessons (greedy approach).

Why the Greedy Approach is Optimal

The cost (number of supplementary lessons required) to eliminate each failing grade is independent per quiz. Since we want to save as many quizzes as possible with a limited budget \(K\), saving them in order of increasing cost yields the optimal solution. This is a typical “special case of the knapsack problem (where each item has equal value),” and the greedy approach gives the optimal solution.

Algorithm

1. For each quiz, if \(H_i > 0\), it is already passing, so skip it.
2. For quizzes with \(H_i \leq 0\), compute the number of supplementary lessons needed to pass: \(\lceil (1 - H_i) / P \rceil\), and store it in a list.
3. Sort this list in ascending order.
4. Starting from the smallest cost, subtract each from the remaining lessons \(K\). Stop when \(K\) is no longer sufficient.
5. The number of quizzes that could not be saved is the answer.

Concrete Example

For \(N=4, K=3, P=2, H = [-3, -1, 5, 0]\):

Quiz	\(H_i\)	Failing?	Lessons Needed
1	\(-3\)	Yes	\(\lceil 4/2 \rceil = 2\)
2	\(-1\)	Yes	\(\lceil 2/2 \rceil = 1\)
3	\(5\)	No	—
4	\(0\)	Yes	\(\lceil 1/2 \rceil = 1\)

Costs in ascending order: \([1, 1, 2]\). Subtracting from \(K=3\) in order: \(3 \to 2 \to 1 \to -1\) (not enough). We can save 2 quizzes, so the number of failing quizzes is \(3 - 2 = 1\).

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (to store the list of costs)

Implementation Notes

• A score of exactly \(0\) is also failing. The passing condition is “\(> 0\)”, not “\(\geq 0\)”.

• The ceiling division must be computed correctly. You can use Python’s math.ceil, or use integer arithmetic: (1 - h + P - 1) // P.

• Although \(K\) and \(H_i\) can be as large as \(10^9\), there is no concern about integer overflow in Python.

  Source Code

import math

def solve():
    N, K, P = map(int, input().split())
    H = list(map(int, input().split()))
    
    # A test is "赤点" (failing) if its final score <= 0
    # We want to minimize the number of failing tests.
    # 
    # For each test i, if H_i > 0, it's already passing (no help needed).
    # If H_i <= 0, we need to add enough P's to make it > 0.
    # The number of补習 needed for test i (if H_i <= 0) is ceil((1 - H_i) / P)
    # = ceil((1 - H_i) / P)
    # Since H_i <= 0, 1 - H_i >= 1, so we need at least 1 session.
    
    # Strategy: greedily fix the cheapest failing tests first.
    
    # Already passing tests (H_i > 0): no cost
    already_passing = sum(1 for h in H if h > 0)
    
    # Failing tests (H_i <= 0): compute cost to fix each
    failing = []
    for h in H:
        if h <= 0:
            # Need final score > 0, i.e., h + k*P > 0 => k > -h/P => k = ceil((-h+1)/P) = ceil((1-h)/P)
            needed = math.ceil((1 - h) / P)
            failing.append(needed)
    
    # Sort by cost (ascending) to fix cheapest first
    failing.sort()
    
    remaining = K
    fixed = 0
    for cost in failing:
        if remaining >= cost:
            remaining -= cost
            fixed += 1
        else:
            break
    
    print(len(failing) - fixed)

solve()

---

This editorial was generated by claude4.6opus-thinking.