AT_abc203_e [ABC203E] White Pawn

题目描述

设 $N$ 为正整数。有一个 $(2N+1)\times (2N+1)$ 的棋盘，行和列的编号分别为 $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)$。

黑色兵不能移动。

请你求出，经过若干次操作后，白色兵最终可以到达 $(2N,Y)$ 的不同 $Y$ 的个数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $X_1$ $Y_1$ $:$ $X_M$ $Y_M$

输出格式

输出答案。

输入输出样例 #1

输入 #1

2 4
1 1
1 2
2 0
4 2

输出 #1

3

输入输出样例 #2

输入 #2

1 1
1 1

输出 #2

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$）
• 所有输入均为整数。

样例解释 1

可以分别如下移动到 $(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$。

样例解释 2

无法将白色兵从 $(0,1)$ 移动到其他位置。

由 ChatGPT 4.1 翻译