Informatica Online Judge

  2014 회장선거 #5 [1172 / 0494]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 73   Total Tried : 152


The Champion of this Problem (C++) : gs19022 - 0ms / 288byte
My Best Submission (C++) : N/A

[koistudy.net (T. HS. Jeon 2014)]

Background

GSHS 회장선거가 끝나고, 본관으로 올라 가려고 한다.

눈이 많이 내려 SRC에서 본관으로 올라가는 길에 있는 계단에 빙판이 생겼다.

n개로 이루어진 계단 중간 중간에 있는 k개의 빙판 계단은 피해 올라가야 한다.

빙판을 밟지 않고 n번째 계단까지 올라갈 수 있는 모든 경우의 수를 구해보자.

단, 계단은 1개 또는 2개만 오를 수 있으며, 처음에 0 번 계단에서 시작한다.

Input

첫 번째 줄에 계단의 길이 n과 빙판 계단의 개수 k가 공백을 두고 입력된다.

두 번째 줄부터 k개의 빙판 계단 위치가 순서대로 입력된다.

[입력값의 정의역]
1<= n <= 20
1<= k <= n

Output

빙판 계단을 피해 n번째 계단까지 올라갈 수 있는 경우의 수를 출력한다.

IO Example

입력예시1
5 3
1
2
5

출력예시1
0

입력예시2
5 2
2
4

출력예시2
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]