White Pawn

题目描述

令 $N$ 为正整数。 我们有一个 $(2N+1)\times (2N+1)$ 的棋盘，行编号为 $0$ 到 $2N$，列也编号为 $0$ 到 $2N$。记 $(i,j)$ 为第 $i$ 行第 $j$ 列的格子。 有一个白兵，初始位于 $(0, N)$。 此外，有 $M$ 个黑兵，第 $i$ 个黑兵位于 $(X_i, Y_i)$。 当白兵位于 $(i, j)$ 时，可以执行以下操作之一来移动它：

如果 $0\leq i\leq 2N-1$, $0 \leq j\leq 2N$ 且 $(i+1,j)$ 不包含黑兵，则将白兵移动到 $(i+1, j)$。 如果 $0\leq i\leq 2N-1$, $0 \leq j\leq 2N-1$ 且 $(i+1,j+1)$ 包含黑兵，则将白兵移动到 $(i+1,j+1)$。 如果 $0\leq i\leq 2N-1$, $1 \leq j\leq 2N$ 且 $(i+1,j-1)$ 包含黑兵，则将白兵移动到 $(i+1,j-1)$。

黑兵不能移动。 求有多少个整数 $Y$，使得可以通过重复这些操作让白兵到达 $(2N, Y)$。

输入格式

输入由标准输入给出，格式如下： $N$ $M$ $X_1$ $Y_1$ : $X_M$ $Y_M$

输出格式

输出答案。

2 4
1 1
1 2
2 0
4 2

3

1 1
1 1

0

提示

$1 \leq N \leq 10^9$ $0 \leq M \leq 2\times 10^5$ $1 \leq X_i \leq 2N$ $0 \leq Y_i \leq 2N$ $(X_i, Y_i) \neq (X_j, Y_j)$ $(i \neq j)$ 输入中的所有数值均为整数。我们可以将白兵移到 $(4,0)$、$(4,1)$ 和 $(4,2)$，过程如下：

$(0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,2)$ $(0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,1)$ $(0,2)\to (1,1)\to (2,0)\to (3,0)\to (4,0)$

另一方面，我们不能将它移到 $(4,3)$ 或 $(4,4)$。 因此，应该输出 $3$.
我们不能将白兵从 $(0,1)$ 移动。

标签: AtCoder|abc203E

来源

AtCoder|abc203E