B58 - Jumping
Editorial
/
Time Limit: 2.5 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 個の足場が横一列に並んでおり、左から順に 1 から N までの番号が付けられています。足場 1 がスタート地点、足場 N がゴール地点であり、足場 i はスタート地点から X_i メートルの位置にあります。
あなたは 1 回で L メートル以上 R メートル以下の距離を右方向にのみジャンプできるとき、スタートからゴールまで最小何回のジャンプで行けますか。ただし、与えられる入力において、スタートからゴールまで到達できることが保証されます。
制約
- 入力はすべて整数である
- 2 \leq N \leq 100000
- 1 \leq L \leq R \leq 10^9
- 0 = X_1 < X_2 < \cdots < X_N \leq 10^9
- 与えられる入力において、スタートからゴールまで到達可能である
入力
入力は以下の形式で標準入力から与えられます。
N L R X_1 X_2 \ldots X_N
出力
答えを出力してください。
入力例 1
5 20 40 0 20 30 60 70
出力例 1
2
まず 30 メートルの距離をジャンプして足場 3 に行き、次に 40 メートルの距離をジャンプして足場 5 に行くのが最適です。