Codeforces Beta Round #51 C. Pie or die（博弈 思维）

C. Pie or die

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Volodya and Vlad play the following game. There are k pies at the cells of n  ×  m board. Each turn Volodya moves one pie to the neighbouring (by side) cell. If the pie lies at the border of the board then Volodya can move it outside the board, get the pie and win. After Volodya's move, Vlad bans some edge at the border of the board of length 1 (between two knots of the board) so that Volodya is not able to move the pie outside the board through this edge anymore. The question is: will Volodya win this game? We suppose both players follow the optimal strategy.

Input

First line contains 3 integers, separated by space: 1 ≤ n, m ≤ 100 — dimensions of the board and 0 ≤ k ≤ 100 — the number of pies. Each of the next k lines contains 2 integers, separated by space: 1 ≤ x ≤ n, 1 ≤ y ≤ m — coordinates of the corresponding pie. There could be more than one pie at a cell.

Output

Output only one word: "YES" — if Volodya wins, "NO" — otherwise.

Examples

input

Copy

2 2 1
1 2

output

Copy

YES

input

Copy

3 4 0

output

Copy

NO

input

Copy

100 50 2
50 25
50 25

output

Copy

NO

题意：两个人博弈，在一张棋盘上，可以移动棋子，一方只要将棋子移出就算胜利，另一方要做的是围堵，每次可以封锁一单位长度，在两个人都足够聪明的情况下判断谁能获胜

思路：这题无关编程算法哈哈，纯属一道思维题，我们可以这样考虑，其实按理来说你在内部走无所谓，但要赢就得有到边界的一步，但是一开始我是想在边界的话你追我堵一定是放棋子的赢，因为边界（左上角，右上角，左下角，右下角）有两个缺口，所以肯定堵不过来，但是如果是在内部一点点的话我就可以腾出步数来修补这些空缺，具体而言只要领先四步即可，所以要求x至少为6或者n-5，n为行数（具体为什么可以推导一下，比如6，距离1有五个空格，四个留着填缺口，最后一步是放棋子先走，所以要五个空），那这道题目就做出来啦

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
template <typename T> inline void read(T& x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
ll n,m,k;
int main()
{
	cin>>n>>m>>k;
	ll flag=1;
	if(!k)
	{
		cout<<"NO"<<endl;
		return 0;
	}
	for(int i=0;i<k;i++)
	{
		ll x,y;
		cin>>x>>y;
		if((x>=6&&x<=n-5)&&(y>=6&&y<=m-5))
		{
			flag=1;
		}
		else 
		{
			flag=0;
			break;
		}
	}
	flag?cout<<"NO"<<endl:cout<<"YES"<<endl;
    return 0;
    
}