B - Toll Gates

コンテスト時間: 2018-04-14(土) 12:10 ~ 2018-04-14(土) 13:50 (100分) AtCoderホームへ戻る

B - Toll Gates 解説

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : $200$ 点

問題文

$N + 1$ 個のマスが左右に一列に並んでいます．これらのマスには，左のマスから順に $0, 1, ..., N$ の番号が付けられています．

あなたは，最初マス $X$ にいます．隣り合うマスの間は自由に移動することができ，マス $0$ またはマス $N$ にたどり着くとゴールすることができます．ただし， $i = 1, 2, ..., M$ について，マス $A_i$ には料金所があり，そのためマス $A_i$ に移動してくる際には $1$ のコストがかかります．なお，マス $0$ ，マス $X$ ，マス $N$ には料金所がないことが保証されます．

ゴールするまでにかかるコストの最小値を求めてください．

制約

$1 \leq N \leq 100$
$1 \leq M \leq 100$
$1 \leq X \leq N - 1$
$1 \leq A_1 < A_2 < ... < A_M \leq N - 1$
$A_i \neq X$
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$   $X$ 
 $A_1$   $A_2$   $...$   $A_M$

出力

ゴールするまでにかかるコストの最小値を出力せよ．

入力例 1Copy

Copy

5 3 3
1 2 4

出力例 1Copy

Copy

次のようにするのが最適です．

まず，マス $3$ から，マス $4$ へ移動する．このとき，マス $4$ には料金所があるので，コスト $1$ がかかる．
次に，マス $4$ から，マス $5$ へ移動する．このときはコストはかからない．
マス $5$ に到着したので，ゴールする．

このようにすると，コストは合計で $1$ になります．

入力例 2Copy

Copy

7 3 2
4 5 6

出力例 2Copy

Copy

まったくコストがかからないこともあります．

入力例 3Copy

Copy

10 7 5
1 2 3 4 6 8 9

出力例 3Copy

Copy

Score : $200$ points

Problem Statement

There are $N + 1$ squares arranged in a row, numbered $0, 1, ..., N$ from left to right.

Initially, you are in Square $X$ . You can freely travel between adjacent squares. Your goal is to reach Square $0$ or Square $N$ . However, for each $i = 1, 2, ..., M$ , there is a toll gate in Square $A_i$ , and traveling to Square $A_i$ incurs a cost of $1$ . It is guaranteed that there is no toll gate in Square $0$ , Square $X$ and Square $N$ .

Find the minimum cost incurred before reaching the goal.

Constraints

$1 \leq N \leq 100$
$1 \leq M \leq 100$
$1 \leq X \leq N - 1$
$1 \leq A_1 < A_2 < ... < A_M \leq N$
$A_i \neq X$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $M$   $X$ 
 $A_1$   $A_2$   $...$   $A_M$

Output

Print the minimum cost incurred before reaching the goal.

Sample Input 1Copy

Copy

5 3 3
1 2 4

Sample Output 1Copy

Copy

The optimal solution is as follows:

First, travel from Square $3$ to Square $4$ . Here, there is a toll gate in Square $4$ , so the cost of $1$ is incurred.
Then, travel from Square $4$ to Square $5$ . This time, no cost is incurred.
Now, we are in Square $5$ and we have reached the goal.

In this case, the total cost incurred is $1$ .

Sample Input 2Copy

Copy

7 3 2
4 5 6

Sample Output 2Copy

Copy

We may be able to reach the goal at no cost.

Sample Input 3Copy

Copy

10 7 5
1 2 3 4 6 8 9

Sample Output 3Copy

Copy