Overview

This problem asks you to find the minimum cost to raise Takahashi’s altitude to at least \(T\), leveraging the fact that the required number of lessons is always exactly one of “0, 1, or impossible.”

Analysis

The operation works as follows: “If you choose a member with a higher altitude than yours, your altitude is immediately updated to theirs.” The key observations are:

• We only need to achieve the goal \(T\); intermediate altitudes don’t matter.
• In a single operation, your altitude becomes exactly the chosen member’s altitude (it’s not an addition).
• Therefore, if there exists a member with altitude \(T\) or higher, you can directly reach it in just 1 lesson by learning from that member (or any member with an equal or higher altitude).

Thus, there are only 3 possible patterns:

1. If \(P \ge T\) already, no operation is needed, so the cost is \(0\).
2. If \(P < T\) but there exists another member with \(S_i \ge T\), you can reach it in 1 lesson, so the cost is \(C\).
3. If \(P < T\) and no member has altitude \(T\) or higher, then no matter how many operations you perform, the highest altitude you can reach is at most the maximum altitude among all members, making it impossible — output \(-1\).

It’s tempting to think about “gradually increasing altitude by learning from multiple members step by step,” but if you eventually reach the same member anyway, taking more steps only increases the cost (since each lesson costs \(C\) yen). Therefore, it suffices to check only “whether we can ultimately reach \(T\) or higher.”

Examples: - \(P=1000,\, T=1500\), and a member with altitude \(2000\) exists → You can reach \(2000\) in 1 lesson, so the answer is \(C\). - \(P=1000,\, T=1500\), and the maximum altitude is \(1400\) → You can only ever reach \(1400\) at most, so it’s impossible — output \(-1\).

Algorithm

1. Read the input.
2. If \(P \ge T\), output 0 and terminate.
3. Otherwise, find the maximum altitude max(S) among members \(2..N\).
   • If max(S) >= T, output C (reachable in 1 lesson).
   • Otherwise, output -1 (unreachable).

※ When \(N=1\), the set \(S\) is empty, so this is treated as “no other member has altitude \(T\) or higher,” resulting in \(-1\) (unless \(P \ge T\), in which case the answer is 0).

Complexity

• Time complexity: \(O(N)\) (just a single pass to find the maximum)
• Space complexity: \(O(N)\) (for storing the input in an array; this can be reduced to \(O(1)\) by reading values one at a time)

Implementation Notes

• If \(P \ge T\), output 0 immediately (avoiding unnecessary computation).

• To avoid errors when \(N=1\) and \(S\) is empty, check whether S is empty before calling max(S) (in the code, this is handled with if S and max(S) >= T:).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, P, T, C = data[0], data[1], data[2], data[3]
    S = data[4:]  # S2..SN (may be empty if N==1)

    if P >= T:
        print(0)
        return

    if S and max(S) >= T:
        print(C)
    else:
        print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.