시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 11 8 30.769%

문제

퀸 게임은 R행 C열 체스판에서 즐길 수 있는 게임이다. 행은 1부터 R까지, 열은 1부터 C까지 번호가 매겨져 있다. 가장 왼쪽 위 사각형은 1행 1열이다.

이 게임은 두명이서 즐기는 게임이다. 체스판 위에는 퀸 N개가 칸에 놓여져 있다. 플레이어는 자신의 턴이 돌아오면, 퀸을 하나 선택한 다음 위쪽 방향, 왼쪽 방향, 왼쪽 위 대각선 방향중 하나로 움직일 수 있다. 움직이는 칸의 수는 제한이 없으나 퀸은 체스판 밖으로 나갈 수 없다. 퀸이 (1,1)에 도착하면, 퀸은 보드에서 제거된다. 마지막 퀸을 보드에서 제거하는 사람이 게임을 이기는 사람이다. 각 칸은 매우 커서 퀸을 무한히 많이 포함할 수 있다. 플레이어는 턴을 번갈아가면서 게임을 한다. 

체스판의 크기와 퀸 N개의 위치가 주어진다. 두 플레이어가 항상 완벽하게 게임을 할 때, 누가 이기는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 R (1 ≤ R ≤ 25), C (1 ≤ C ≤ 1015), N (1 ≤ N ≤ 1000)이 주어진다. 다음 N개 줄에는 퀸의 위치가 주어진다. 첫 번째 숫자는 행 번호이고, 두 번째 숫자는 열 번호이다.

출력

각 테스트 케이스 마다 첫 번째 플레이어가 이기는 전략을 가지고 있으면 "YES"를, 아니면 "NO"를 출력한다.

예제 입력 1

3
5 5 1
2 3
5 5 2
4 4
4 4
5 5 3
1 2
2 1
2 2

예제 출력 1

NO
NO
YES
W3sicHJvYmxlbV9pZCI6IjU2NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwMzggXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwMzggXHVhYzhjXHVjNzg0XHVjNzQwIFJcdWQ1ODkgQ1x1YzVmNCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDBcdWMxMWMgXHVjOTkwXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWQ1ODlcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBSXHVhZTRjXHVjOWMwLCBcdWM1ZjRcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBDXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgMVx1ZDU4OSAxXHVjNWY0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjQ1MFx1YmE4NVx1Yzc3NFx1YzExYyBcdWM5OTBcdWFlMzBcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWNjYjRcdWMyYTRcdWQzMTAgXHVjNzA0XHVjNWQwXHViMjk0IFx1ZDAzOCBOXHVhYzFjXHVhYzAwIFx1Y2U3OFx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1ZDEzNFx1Yzc3NCBcdWIzY2NcdWM1NDRcdWM2MjRcdWJhNzQsIFx1ZDAzOFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjMTIwXHVkMGRkXHVkNTVjIFx1YjJlNFx1Yzc0YyBcdWM3MDRcdWNhYmQgXHViYzI5XHVkNWE1LCBcdWM2N2NcdWNhYmQgXHViYzI5XHVkNWE1LCBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1YjMwMFx1YWMwMVx1YzEyMCBcdWJjMjlcdWQ1YTVcdWM5MTEgXHVkNTU4XHViMDk4XHViODVjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YzIxOFx1YjI5NCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHVjNWM2XHVjNzNjXHViMDk4IFx1ZDAzOFx1Yzc0MCBcdWNjYjRcdWMyYTRcdWQzMTAgXHViYzE2XHVjNzNjXHViODVjIFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWQwMzhcdWM3NzQgKDEsMSlcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViYTc0LCBcdWQwMzhcdWM3NDAgXHViY2Y0XHViNGRjXHVjNWQwXHVjMTFjIFx1YzgxY1x1YWM3MFx1YjQxY1x1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1ZDAzOFx1Yzc0NCBcdWJjZjRcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNzc0XHVhZTMwXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjZWU0XHVjMTFjIFx1ZDAzOFx1Yzc0NCBcdWJiMzRcdWQ1NWNcdWQ3ODggXHViOWNlXHVjNzc0IFx1ZDNlY1x1ZDU2OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVkMTM0XHVjNzQ0IFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwXHVjNjQwIFx1ZDAzOCBOXHVhYzFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVkNTZkXHVjMGMxIFx1YzY0NFx1YmNiZFx1ZDU1OFx1YWM4YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTYwIFx1YjU0YywgXHViMjA0XHVhYzAwIFx1Yzc3NFx1YWUzMFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgUiAoMSAmbGU7IFIgJmxlOyAyNSksIEMgKDEgJmxlOyBDICZsZTsgMTA8c3VwPjE1PFwvc3VwPiksIE4gKDEgJmxlOyBOICZsZTsgMTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMDM4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDU4OSBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1YzVmNCBcdWJjODhcdWQ2MzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWM4MDRcdWI3YjVcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3NCAmcXVvdDtZRVMmcXVvdDtcdWI5N2MsIFx1YzU0NFx1YjJjOFx1YmE3NCAmcXVvdDtOTyZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTY0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlF1ZWVuIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPlF1ZWVuIGdhbWUgaXMgcGxheWVkIGluIGEgY2hlc3Nib2FyZCBvZiBzaXplIFIgcm93cyBhbmQgQyBjb2x1bW5zLiBSb3dzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gUiBhbmQgY29sdW1ucyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIEMuIFRoZSB0b3Btb3N0IHNxdWFyZSBpcyBpbiByb3cgMSBhbmQgY29sdW1uIDEuIFRoZSBnYW1lIGlzIGEgMiBwbGF5ZXIgZ2FtZS4gSW5pdGlhbGx5IHRoZXJlIGFyZSBOIHF1ZWVucyBwbGFjZWQgaW4gdmFyaW91cyBzcXVhcmVzIG9mIHRoZSBjaGVzc2JvYXJkLiBJbiBoaXMgdHVybiwgdGhlIHBsYXllciBwaWNrcyBhIHF1ZWVuIGFuZCBtb3ZlcyBpdCBlaXRoZXIgdG93YXJkcyB0aGUgdG9wIHZlcnRpY2FsbHksIG9yIHRvd2FyZHMgdGhlIGxlZnQgaG9yaXpvbnRhbGx5IG9yIHRvd2FyZHMgdGhlIHRvcC1sZWZ0IGRpYWdvbmFsbHkgYW5kIHRoZSBxdWVlbiBzaG91bGQgYWx3YXlzIHN0YXkgb24gdGhlIGJvYXJkLiBXaGVuIHRoZSBxdWVlbiByZWFjaGVzIHNxdWFyZSAoMSwgMSkgaXQgaXMgcmVtb3ZlZCBmcm9tIHRoZSBib2FyZC4gVGhlIHBsYXllciB3aG8gZ2l2ZXMgdGhlIGxhc3QgbW92ZSB3aW5zLiBFYWNoIHNxdWFyZSBpcyBiaWcgZW5vdWdoIHRvIGFjY29tbW9kYXRlIGluZmluaXRlIG51bWJlciBvZiBxdWVlbnMuIFRoZSBwbGF5ZXJzIGdpdmUgdGhlaXIgbW92ZXMgYnkgdHVybnMuIFlvdSBhcmUgZ2l2ZW4gdGhlIHNpemUgb2YgdGhlIGNoZXNzYm9hcmQgYW5kIHRoZSBpbml0aWFsIHBvc2l0aW9ucyBvZiB0aGUgTiBxdWVlbnMuIEFzc3VtaW5nIHRoYXQgYm90aCBvZiB0aGUgcGxheWVycyBwbGF5IHBlcmZlY3RseSB5b3VyIHRhc2sgaXMgdG8gZGV0ZXJtaW5lIHdobyB3aWxsIHdpbiB0aGlzIGdhbWUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBUIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgMyBpbnRlZ2VycyBSKDEmbGU7UiZsZTsyNSksIEMoMSZsZTtDJmxlOzEwPHN1cD4xNTxcL3N1cD4pIGFuZCBOKDEmbGU7TiZsZTsxMDAwKS4gRWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIHRoZSBwb3NpdGlvbnMgb2YgTiBxdWVlbnMuIFRoZSBwb3NpdGlvbiBpcyBkZW5vdGVkIGJ5IHR3byBpbnRlZ2Vycy4gVGhlIGZpcnN0IGludGVnZXIgaXMgdGhlIHJvdyBudW1iZXIgYW5kIHRoZSBzZWNvbmQgaW50ZWdlciBpcyB0aGUgY29sdW1uIG51bWJlcnMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCAmbGRxdW87WUVTJnJkcXVvOyBpZiB0aGUgZmlyc3QgcGxheWVyIGhhcyBhIHdpbm5pbmcgc3RyYXRlZ3kgYW5kICZsZHF1bztOTyZyZHF1bzsgb3RoZXJ3aXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ICPC > Regionals > Asia Pacific > Thailand > 2011 ACM-ICPC Asia Phuket Regional Programming Contest E번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: newdeal