Overview

This problem asks us to find the minimum number of strength potions the player needs to use in order to reach the top floor of the dungeon.

Analysis

In this problem, given an initial combat power \(S\), we need to use at most \(K\) strength potions to be able to defeat all monsters.

A Naive Approach Is Difficult

For example, if we try simulating by incrementally increasing the number of potions used one by one, the worst case takes an enormous amount of time (requiring up to \(K\) simulations). Since \(K\) can be up to \(10^{18}\), this is not practical.

Key Observation

When the initial combat power after using potions is \(P = S + x\) (where \(x\) is the number of potions used),
if \(x\) potions are enough to defeat all monsters, then using more potions will also certainly succeed.
In other words, the condition of “whether a certain number of potions leads to success” has monotonicity.

By leveraging this monotonicity, we can efficiently find the minimum number of potions to use via binary search.

Algorithm

1. Perform binary search on the number of potions used, denoted as mid.
2. For each mid, simulate with an initial combat power of \(S + mid\) and check whether all monsters can be defeated.
3. If all monsters are defeated, fewer potions might also work, so we narrow the search range (right = mid - 1).
4. If not all monsters are defeated, more potions are needed, so we set left = mid + 1.
5. Finally, find the minimum mid that satisfies the condition.

Complexity

• Time complexity: \(O(N \log K)\)
  • Binary search runs \(O(\log K)\) times, each requiring an \(O(N)\) simulation.
• Space complexity: \(O(N)\)
  • The size of the array storing the monsters’ strengths.

Implementation Notes

• The binary search range is set as left = 0, right = min(K, 10**18) (to handle cases where \(K\) is very large).

• Combat power is updated with current_power += e, and care must be taken regarding overflow (not an issue in Python).

• Don’t forget to output -1 when the condition cannot be satisfied.

  Source Code

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = int(data[1])
    K = int(data[2])
    
    E = list(map(int, data[3:]))

    # Binary search on the number of enhancement potions needed
    left, right = 0, min(K, 10**18)
    answer = -1
    
    while left <= right:
        mid = (left + right) // 2
        current_power = S + mid
        
        success = True
        for e in E:
            if current_power >= e:
                current_power += e
            else:
                success = False
                break
        
        if success:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
            
    print(answer)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.