問題一覧 > 通常問題

No.3252 Constrained Moving

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 98
作問者 : Iroha_3856 / テスター : lif4635 champignon tikuwa_
ProblemId : 12630 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-05 16:06:59

問題文

正整数 $N, S, T, K$ と、長さ $N$ の整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。

今、変数 $i$ が $i = S$ で初期化されています。

あなたは、以下の操作を好きなだけ行って、$i = T$ とするのが目標です。

  • 操作:$A_i + A_j \leq K$ となるような $j$ を選び、$i$ を $j$ に変更する。

$i = T$ とするのにかかる操作の最小回数を出力してください。ただし、$i = T$ とすることが不可能な場合、$-1$ を出力してください。

入力

$N\ S\ T\ K$
$A_1\ A_2\ \ldots\ A_N$

入力は全て以下の制約を満たす。

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq S, T \leq N$
  • $S \neq T$
  • $1 \leq A_i \leq 10^9$
  • $1 \leq K \leq 10^9$
  • 入力は全て整数

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1
入力
3 1 3 9
5 4 5
出力
2

はじめ、$i = 1$ です。

$A_1 + A_2 = 9 \leq 9$ なので、$i = 2$ に変更します。

$A_2 + A_3 = 9 \leq 9$ なので、$i = 3$ に変更します。

$i = 3$ にするという目標が $2$ 回の操作で達成できました。

$1$ 回の操作で $i = 3$ とすることはできないので、$2$ を出力します。

サンプル2
入力
2 1 2 1
61 99
出力
-1

$i = 1$ の状態から $i = 2$ とすることは不可能です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。