Overview

This is a simple simulation problem where you visit dungeon rooms from left to right, defeat monsters if you have enough health, and skip them otherwise. You output the number of skipped rooms multiplied by the penalty unit cost \(C\).

Analysis

The key point of this problem is that Takahashi has no room for choice in his actions.

• Rooms are processed from left to right (the order is fixed)
• Monsters that can be defeated must be defeated (no decision-making needed on whether to fight)
• Rooms with monsters that cannot be defeated must be skipped

In other words, no advanced algorithms like greedy methods or dynamic programming are needed — you can obtain the correct answer simply by simulating from left to right according to the rules described in the problem statement.

Verification with a Concrete Example

For example, with \(N = 3, S = 10, C = 5\) and rooms \((H, P) = (8, 3), (7, 2), (4, 1)\):

The number of skips is \(1\), so the penalty is \(1 \times 5 = 5\).

Algorithm

1. Set the current health hp to the initial health \(S\), and set the skip count skip_count to \(0\).
2. Process rooms \(i = 1, 2, \ldots, N\) in order:
   • If hp \(\geq H_i\), defeat the monster: hp \(\leftarrow\) hp \(- H_i + P_i\)
   • If hp \(< H_i\), skip: skip_count \(\leftarrow\) skip_count \(+ 1\)
3. Output the final penalty skip_count \(\times C\).

Complexity

• Time complexity: \(O(N)\) — each room is processed exactly once
• Space complexity: \(O(1)\) — only variables for health and skip count are needed (excluding input reading)

Implementation Notes

• Health values can become very large: \(S\) can be up to \(10^9\), \(P_i\) can also be up to \(10^9\), and \(N\) can be up to \(2 \times 10^5\), so health can reach approximately \(10^9 + 2 \times 10^5 \times 10^9 \approx 2 \times 10^{14}\). In Python, integer overflow does not occur, but in C++ and similar languages, you need to use long long.

• Fast input: Since \(N\) can be up to \(2 \times 10^5\), in Python we use sys.stdin.buffer.read() to read all input at once for faster I/O.

• Penalty calculation: It is simpler to count the number of skips and multiply by \(C\) at the end, rather than adding the penalty each time.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    C = int(input_data[idx]); idx += 1
    
    skip_count = 0
    hp = S
    
    for i in range(N):
        H = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        
        if hp >= H:
            hp = hp - H + P
        else:
            skip_count += 1
    
    print(skip_count * C)

main()

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