Overview

This problem asks us to find the minimum number of power-up potions Takahashi needs to use in order to reach the top floor of the dungeon. Using a power-up potion increases his initial combat power, and he must satisfy the condition to defeat the monster on each floor.

Analysis

The core of the problem is determining how many power-up potions are needed to break through all floors. A naive approach would be to try each number of potions from 0 to K in order, but since K can be up to \(10^{18}\), exhaustive search is clearly impossible.

The key observation is that the initial combat power when using x potions is S+x, and there is a monotonicity property: if this value is large enough, all monsters can be defeated. In other words, when x is small, Takahashi loses partway through, but once x reaches a certain value or above, he can always clear the dungeon. By leveraging this monotonicity, we can efficiently find the minimum x using binary search.

Algorithm

1. First, check whether the dungeon can be cleared using 0 potions (initial combat power S). If so, output 0.
2. Next, if the dungeon cannot be cleared even when using the maximum number of potions K, output -1.
3. Otherwise, perform binary search. The search range is [0, K], and for each midpoint mid, we use the can_reach(mid) function to determine if clearing is possible.
   • can_reach(x) function: Set the initial combat power to S+x, then fight the monsters on each floor in order. If the current combat power is greater than or equal to the monster’s strength, add to the combat power; otherwise, return false. If all floors are cleared, return true.
4. The minimum x found by binary search is the answer.

Complexity

• Time complexity: \(O(N \log K)\)
  • The number of binary search iterations is \(\log K\)
  • Each iteration requires \(O(N)\) to check all N floors
  • Combined: \(O(N \log K)\)
• Space complexity: \(O(N)\)
  • For the array storing the monsters’ strengths

Implementation Notes

• As initial conditions for the binary search, we first check the cases of 0 and K potions to avoid unnecessary computation.

• Inside the can_reach function, the current combat power is updated by adding after defeating a monster, correctly simulating the change in combat power.

• Since we handle large numbers (up to \(10^{18}\)), integer overflow must be considered. However, in Python this is not an issue since it automatically handles arbitrary-precision integers.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    N = int(data[0])
    S = int(data[1])
    K = int(data[2])
    E = list(map(int, data[3:3+N-1]))
    
    left = 0
    right = K
    answer = -1
    
    def can_reach(x):
        current = S + x
        for i in range(N-1):
            if current < E[i]:
                return False
            current += E[i]
        return True
    
    if can_reach(0):
        print(0)
        return
        
    if not can_reach(K):
        print(-1)
        return
        
    while left <= right:
        mid = (left + right) // 2
        if can_reach(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
            
    print(answer)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.