Overview

This is a problem of finding the maximum number of balloons you can pop out of \(N\) balloons. The optimal strategy is to use only the dart with the highest attack power and greedily pop balloons starting from those with the lowest durability.

Analysis

Key Insight ①: Only the strongest dart needs to be used

It is optimal to use only the dart with the highest attack power (let this be \(P_{\max}\)) among the \(M\) darts. This is because for any balloon, repeatedly throwing the dart with the maximum attack power requires the fewest number of throws to pop it. There is no reason to use darts with lower attack power.

Key Insight ②: Number of throws needed to pop each balloon

When balloon \(i\) has durability \(H_i\) and we reduce it by \(P_{\max}\) each time, the number of throws needed to pop it is:

\[\left\lceil \frac{H_i}{P_{\max}} \right\rceil\]

For example, if \(H_i = 10\) and \(P_{\max} = 3\), then \(\lceil 10/3 \rceil = 4\) throws will reduce the durability to \(10 - 3 \times 4 = -2 \leq 0\), popping the balloon.

Key Insight ③: Pop balloons with the smallest cost first (greedy method)

Since we want to maximize the number of balloons popped within at most \(K\) throws, it is optimal to prioritize popping balloons with the smallest required number of throws (cost). We sort by cost in ascending order and keep popping as long as the cumulative sum does not exceed \(K\).

Comparison with a naive approach

Considering all combinations of balloons and darts would lead to an explosion in computational complexity, but the observation that “only the strongest dart needs to be used” greatly simplifies the problem.

Algorithm

1. Find the maximum attack power of the darts: \(P_{\max} = \max(P_1, P_2, \ldots, P_M)\).
2. For each balloon \(i\), compute the number of throws needed to pop it: \(c_i = \lceil H_i / P_{\max} \rceil\).
3. Sort \(c_i\) in ascending order.
4. Accumulate \(c_i\) from the smallest, incrementing the count as long as the cumulative sum is at most \(K\).
5. That count is the answer.

Concrete example: For \(N=3\), \(M=2\), \(K=5\), \(H=[7, 3, 10]\), \(P=[3, 4]\):

• \(P_{\max} = 4\)
• Cost for each balloon: \(\lceil 7/4 \rceil = 2\), \(\lceil 3/4 \rceil = 1\), \(\lceil 10/4 \rceil = 3\)
• After sorting: \([1, 2, 3]\)
• Cumulative sums: \(1, 3, 6\)
• Since \(K=5\): \(1+2=3 \leq 5\) ✓, \(1+2+3=6 > 5\) ✗
• Answer: 2

Complexity

• Time complexity: \(O(N \log N + M)\)
  • Finding the maximum among \(M\) darts: \(O(M)\)
  • Computing costs for \(N\) balloons: \(O(N)\)
  • Sorting: \(O(N \log N)\)
  • Scanning the cumulative sum: \(O(N)\)
• Space complexity: \(O(N + M)\) (for storing input and the cost array)

Implementation Notes

• Ceiling division can be computed using only integer arithmetic as (H + P_max - 1) // P_max. When using Python’s math.ceil, floating-point errors may occur for large integers, so integer arithmetic is safer.

• Since \(K\) and \(H_i\) can be as large as \(10^{18}\), care must be taken to avoid overflow (in Python, this is not an issue since integers have no size limit).

• By breaking out of the loop as soon as the cumulative sum exceeds \(K\), unnecessary computation can be avoided.

  Source Code

import sys
from math import ceil

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    H = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    P = [int(input_data[idx + i]) for i in range(M)]
    idx += M
    
    # Use the strongest dart
    max_P = max(P)
    
    # For each balloon, compute minimum number of throws to break it
    # ceil(H_i / max_P)
    # To break a balloon with durability H using dart with power max_P:
    # need ceil(H / max_P) throws
    
    costs = []
    for h in H:
        costs.append((h + max_P - 1) // max_P)
    
    # Sort costs in ascending order - break cheapest balloons first
    costs.sort()
    
    # Use prefix sums to find maximum number of balloons we can break with K throws
    # Binary search or just prefix sum scan
    
    count = 0
    total = 0
    for c in costs:
        total += c
        if total <= K:
            count += 1
        else:
            break
    
    print(count)

solve()

---

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