TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

Portal 是一款拿著傳送槍跑來跑去的解謎遊戲,老張想要做一款對它抄襲致敬的遊戲,名字叫 Partol。遊戲是在一個一維世界中進行的,以 $[0,1,\ldots,n-1]$ 代表位置,玩家會從位置 $0$ 開始進行遊戲,目標是走到位置 $p$ 的出口。
操作方式如下,每個回合玩家可以選擇往左走 $l$ 步或往右走 $r$ 步,如果走超過邊界,也就是位置 $<0$ 或 $>n-1$ 會 Game Over。

回合結束時,如果玩家停在位置 $i$,且 $s(i) \neq i$,則玩家會被神秘的量子物理傳送門傳送到 $s(i)$,有些 $s(i)$ 會比 $n$ 還大,這些傳送門會把玩家丟到虛空,也會導致 Game over。保證 $s(0) = 0, s(p) = p$(起點與出口是不動點),並且 $s(s(i)) = s(i) \ \ \forall s(i) \in [0,n-1]$,也就是不會發生連續傳送的現象。老張想要知道從起點走到出口最少要幾個回合,請幫他算算看。如果沒辦法走出口,也告訴他一聲。

Input Format

第一行有 $4$ 個整數 $n,p,l,r$,分別代表遊戲空間長度,目標位置,往左/右移動的距離。
第二行有 $n$ 個整數,代表 $s(0),s(1),...,s(n-1)$。

  • $2 \leq n \leq 10^ 6$
  • $1 \leq p \leq n-1$
  • $1 \leq l,r \leq n-1$
  • $-10^ 8 \leq s(i) \leq 10^ 8, \forall i$

Output Format

從起點走到出口最少要幾個回合,如果沒辦法走到出口,請輸出 $-1$。

Sample Input 1

5 3 1 2
0 3 2 3 5

Sample Output 1

2

Sample Input 2

10 8 2 3
0 5 2 3 4 5 6 6 8 9

Sample Output 2

3

Hints

Problem Source

APCS 考古 201910

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~35 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 65536 1 2
1 5000 524288 65536 1 2
2 5000 524288 65536 2
3 5000 524288 65536 2
4 5000 524288 65536 2
5 5000 524288 65536 2
6 5000 524288 65536 2
7 5000 524288 65536 2
8 5000 524288 65536 2
9 5000 524288 65536 2
10 5000 524288 65536 2
11 5000 524288 65536 2
12 5000 524288 65536 2
13 5000 524288 65536 2
14 5000 524288 65536 2
15 5000 524288 65536 2
16 5000 524288 65536 2
17 5000 524288 65536 2
18 5000 524288 65536 2
19 5000 524288 65536 2
20 5000 524288 65536 2
21 5000 524288 65536 2
22 5000 524288 65536 2
23 5000 524288 65536 2
24 5000 524288 65536 2
25 5000 524288 65536 2
26 5000 524288 65536 2
27 5000 524288 65536 2
28 5000 524288 65536 2
29 5000 524288 65536 2
30 5000 524288 65536 2
31 5000 524288 65536 2
32 5000 524288 65536 2
33 5000 524288 65536 2
34 5000 524288 65536 2
35 5000 524288 65536 2