No.3252 Constrained Moving
タグ : / 解いたユーザー数 124
作問者 :
Iroha_3856
/ テスター :
lif4635
champignon
tikuwa_
Problem Statement
You are given positive integers $N, S, T, K$ and an integer sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$.
Initially, a variable $i$ is initialized to $i = S$.
Your goal is to make $i = T$ by performing the following operation any number of times.
- Operation: choose $j$ such that $A_i + A_j \leq K$, and change $i$ to $j$.
Output the minimum number of operations required to make $i = T$. If it is impossible to make $i = T$, output $-1$.
Input
$N\ S\ T\ K$ $A_1\ A_2\ \ldots\ A_N$
All input satisfies the following constraints.
- $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$
- All input values are integers.
Output
Output the answer, followed by a newline.
Sample
Sample 1
Input
3 1 3 9 5 4 5
Output
2
Initially, $i = 1$.
Since $A_1 + A_2 = 9 \leq 9$, we change it to $i = 2$.
Since $A_2 + A_3 = 9 \leq 9$, we change it to $i = 3$.
The goal of making $i = 3$ has been achieved in $2$ operations.
It is not possible to make $i = 3$ in $1$ operation, so output $2$.
Sample 2
Input
2 1 2 1 61 99
Output
-1
It is impossible to reach $i = 2$ from the state $i = 1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。