2018-软工机试-D-定西

单点时限: 1.0 sec

内存限制: 256 MB

这么多年你一个人一直在走
方向和天气的节奏会让你忧愁
你说你遇见了一大堆奇怪的人
他们看上去好像都比你开心
——李志《定西》

这首歌的吉他节奏总感觉是在致敬《加州旅馆》，前奏又像葫芦娃里面在蛇精洞是的配乐

一个人走走了很多年，发现自己走到了一个很长的，年久失修的楼梯面前。年久失修的意思就是，有 k 个台阶坏了，没法走。

楼梯一共有 n 层，你一次能上一阶、两阶或三阶台阶，请问，你从楼梯底部 (0 开始) 走到楼梯顶部，共有多少种走法。

输入格式

输入数据共两行，第一行包含两个自然数 n (1≤n≤100 ) 和 k (0≤k<n )，第二行包含 k 个自然数 Xi (1≤Xi≤n )，数字之间用一个空格隔开，表示损坏的台阶的序号（从楼梯底部到楼梯顶部，台阶序号依次为 1 到 n ）。

输出格式

输出数据仅包含一个整数，表示所有可行走法的总数。

样例

Input

5 2
2 4

Output

 1 #include<stdio.h>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 int a[105];
10 int sum,n;
11 
12 void dfs(int p)
13 {
14     if(p==n)
15     {
16         sum++;
17         return;
18     }
19     else
20     {
21         if(a[p+1]==1&&(p+1<=n))
22             dfs(p+1);
23 
24         if(a[p+2]==1&&(p+2<=n))
25             dfs(p+2);
26         
27         if(a[p+3]==1&&(p+3<=n))
28             dfs(p+3);
29     }
30     return;
31 }
32 
33 int main()
34 {
35     int k,d;
36     scanf("%d%d",&n,&k);
37     sum=0;
38     for(int i=0;i<105;i++)
39         a[i]=1;
40     for(int j=0;j<k;j++)
41     {
42         scanf("%d",&d);
43         a[d]=0;
44     }
45     dfs(0);
46     printf("%d",sum);
47     return 0;
48 }