ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5998: 芯片

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：2 通过：2
提交提交记录统计Web Board

题目描述

杰拉尔德玩下面的游戏。他有一个大小为n×n个细胞的方格场，其中m个不同的细胞被禁止。在比赛之前，他必须在一些边框（但不是角落）板上放置一些筹码。然后，在n-1分钟内，杰拉尔德每分钟将每个芯片移动到相邻的单元中。他将每个芯片从其原始边缘移动到相反的边缘。杰拉尔德在这场比赛中输了三种情况：
  • 至少有一个芯片至少一次落入被禁止的细胞。
  • 至少有一次两个芯片在同一单元上。
  • 至少一次两个筹码在一分钟内交换（例如，如果您将两个筹码放在一行长度均匀的两个相对边框单元格上，则这种情况发生在行的中间）。
在这种情况下，他输了，赚了0分。当没有发生这样的事情时，他赢了并获得的积分等于他设法放在棋盘上的筹码数量。帮助杰拉尔德获得最多的积分。

例子
输入  
							

								3 1 
							


							

								2 2

输出

0

输入

3 0

输出

1

输入  
							

								4 3 
							


							

								3 1 
							


							

								3 2 
							


							

								3 3

输出

1

输入格式

第一行包含两个空格分隔的整数 n 和 m （2≤n≤1000， 0≤m≤105） - 字段的大小和禁止单元格的数量。接下来的 m 行各包含两个空格分隔的整数。具体来说，这些行的第 i 条包含数字 x i 和 y i （1≤x i，y i≤n） − 第 i 个禁止单元格的坐标。所有给定的单元格都是不同的。
考虑从上到下从 1 到 n 编号的字段行，以及从左到右从 1 到 n 的列 −。

输出格式

打印一个整数 - 杰拉尔德在这个游戏中可以获得的最高积分。

输入样例 复制 

4 3
3 1
3 2
3 3

输出样例 复制 

1

数据范围与提示

在第一个测试中，答案等于零，因为我们不能将芯片放入角落单元格中。
在第二个样本中，我们可以将一个芯片放入电池 （1， 2）、电池 （3， 2）、电池 （2， 1） 或电池 （2， 3） 中。我们不能放置两个筹码。
在第三个样本中，我们只能将一个芯片放入电池（2，1）或电池（2，4）中。

分类标签