Overview

This is a problem where you choose the optimal dart from multiple available darts and pop as many balloons as possible within a limited number of throws.

Analysis

The key observations for solving this problem are the following two points:

1. Which dart should you use? Each dart can be used any number of times. Since a higher durability reduction per throw is always better, it is always optimal to keep using only the dart with the maximum attack power. There is absolutely no benefit to choosing a dart with lower attack power.

2. Which balloon should you target first? Since we want to maximize the number of popped balloons, it is optimal to prioritize targeting balloons that can be popped with fewer throws (greedy approach).

If you perform a naive simulation where each throw reduces a balloon’s durability one step at a time, the number of throws \(K\) can be as large as \(10^{18}\), which would result in a Time Limit Exceeded (TLE). Therefore, we need to use division to calculate “the number of throws needed to pop each balloon” all at once.

When continuously using the dart with maximum attack power, the number of throws needed to pop a balloon with durability \(H_i\) can be calculated as follows: $\( \lceil H_i \div (\text{maximum attack power}) \rceil \)\( (\)\lceil x \rceil\( represents the smallest integer greater than or equal to \)x$, i.e., ceiling)

After that, we can obtain the correct answer by popping balloons in order from those requiring the fewest throws, as long as the total number of throws does not exceed \(K\).

Algorithm

1. Find the maximum value max_P among the dart attack powers \(P_1, P_2, \ldots, P_M\).
2. For each balloon, calculate the number of throws needed to pop it \(\lceil H_i / \text{max\_P} \rceil\) and store it in a list.
3. Sort the list of “required number of throws” in ascending order (smallest first).
4. Iterate through the list from the beginning, subtracting the required number of throws from the remaining throw count \(K\).
5. When \(K\) becomes insufficient (or all balloons have been popped), stop and output the number of popped balloons.

Complexity

• Time complexity: \(O(N \log N + M)\)
  • Finding the maximum dart attack power: \(O(M)\)
  • Calculating the required throws for each balloon: \(O(N)\)
  • Sorting the required throws: \(O(N \log N)\)
  • Processing the balloon popping: \(O(N)\)
  • Overall \(O(N \log N + M)\), which is sufficiently fast under the given constraints.
• Space complexity: \(O(N + M)\)
  • Memory is used for storing input data and the list of required throws for each balloon.

Implementation Notes

When calculating the number of throws needed to pop a balloon, you need to perform “ceiling division.” If you use floating-point numbers like math.ceil(H_i / max_P) in Python, there is a risk of precision errors leading to Wrong Answer (WA) when the numbers are very large.

To prevent this, use the technique of computing entirely with integers. The ceiling of dividing integer \(A\) by \(B\) can be written as follows: $\( (A + B - 1) \mathbin{//} B \)$ (// denotes floor division)

For example, if a balloon’s durability is \(A = 7\) and the maximum attack power is \(B = 3\), the required number of throws is \(3\). Substituting into the formula: \((7 + 3 - 1) \mathbin{//} 3 = 9 \mathbin{//} 3 = 3\), confirming it calculates correctly. This is a frequently used technique in competitive programming, so it’s worth remembering.

Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    H = [int(x) for x in input_data[3:3+N]]
    P = [int(x) for x in input_data[3+N:3+N+M]]
    
    max_P = max(P)
    
    costs = [(h + max_P - 1) // max_P for h in H]
    costs.sort()
    
    ans = 0
    for c in costs:
        if K >= c:
            K -= c
            ans += 1
        else:
            break
            
    print(ans)

if __name__ == '__main__':
    solve()

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