概要

高橋君の標高を \(T\) 以上にするために、必要なレッスン回数が「0 回か 1 回か（不可能）」のどれかに必ず決まることを利用して、最小費用を求める問題です。

考察

この操作は「自分より高い標高の会員を選ぶと、その標高に一気に更新される」というものです。ここで重要な観察は次の通りです。

• 目標 \(T\) を達成したいだけであり、途中経過の標高は問われない。
• 1 回の操作で、選んだ会員の標高にそのままなれる（加算ではない）。
• つまり、もし \(T\) 以上の標高を持つ会員がいるなら、その会員（または同等以上の会員）に 直接 1 回で 師事すればよい。

よって必要なレッスン回数は以下の 3 パターンしかありません。

1. すでに \(P \ge T\) なら、操作不要なので費用は \(0\)。
2. \(P < T\) だが、他の会員の中に \(S_i \ge T\) が存在するなら、1 回で到達できるので費用は \(C\)。
3. \(P < T\) かつ、誰も \(T\) 以上でないなら、何回操作しても最高到達標高は最大でも「会員の最大値」までしか上がらないため不可能で \(-1\)。

素朴に「何回も師事して段階的に上げる」ことを考えてしまいがちですが、段階を踏んでも最終的に同じ会員に到達するなら回数が増えるだけで損です（各回 \(C\) 円かかるため）。したがって「最終的に \(T\) 以上になれるか」だけを見れば十分です。

例： - \(P=1000,\, T=1500\)、会員に \(2000\) がいる → 1 回で \(2000\) になれるので答えは \(C\)。 - \(P=1000,\, T=1500\)、最大が \(1400\) → どこまで行っても \(1400\) 止まりなので不可能で \(-1\)。

アルゴリズム

1. 入力を受け取る。
2. もし \(P \ge T\) なら 0 を出力して終了。
3. そうでなければ、会員 \(2..N\) の標高の最大値 max(S) を調べる。
   • max(S) \ge T なら C を出力（1 回で到達可能）。
   • そうでなければ -1 を出力（到達不可能）。

※ \(N=1\) のときは \(S\) が空になるので、その場合も「他に \(T\) 以上の会員がいない」扱いで -1（ただし \(P \ge T\) なら 0）になります。

計算量

• 時間計算量: \(O(N)\)（最大値を 1 回走査するだけ）
• 空間計算量: \(O(N)\)（入力を配列として保持するため。逐次読み取りにすれば \(O(1)\) にもできます）

実装のポイント

• \(P \ge T\) の場合は即座に 0 を出力してよい（無駄な計算をしない）。

• \(N=1\) で \(S\) が空でも落ちないように、S が空かどうかを確認してから max(S) を使う（コードでは if S and max(S) >= T: としている）。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。