[POI2004]平板游戏

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file gra.in Output file gra.out

【题目描述】

让我们考虑一个在1行m列矩形网格上的游戏。这张网格共有m格,从左到右被命名为1到m。网格上有n个棋子,每个都独占一格。没有棋子占据m号格。每回合如下:该回合进行移动的玩家任意选择一枚棋子,并且把它放到第一个编号更大的空格子中。两名玩家轮流进行移动。把棋子放在最后一格,也就是m号格子的玩家胜利。

下图给出了一个例子(m=7),现在玩家可以把棋子从2移动到4,从3移动到4或者从6移动到7.

我们说玩家的一个移动可以获胜,如果在此之后无论对手如何移动,他都能获胜。

写一个程序来完成以下任务:

·读入棋盘的规模和最初棋子的位置。

·计算在这种情况下先手可以获胜的不同移动方案数。

·输出结果。

【输入格式】

输入文件的第一行有两个空格隔开的整数m,n(2<=m<=10^9,1<=n<=10^6,n<m)。

第二行有n个递增整数,即最开始棋子的位置。这些整数由空格隔开。

【输出格式】

输出一行一个整数,即对于所给开局,先手可以获胜的不同移动方案数。

【样例输入】

输入样例1:

5 2

1 3


输入样例2:

5 2

2 3

【样例输出】

输出样例1:

1


输出样例2:

0

【来源】

POI 2003/2004 I stage Game