시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 501 | 205 | 170 | 43.702% |
재헌이는 생일 선물로 크기가 $N \times N$인 체스판과 백색 킹 하나, 흑색 퀸 $100\ 000$개를 받았다. 킹은 8방향(상하좌우 및 대각선)으로 한 칸씩 이동할 수 있고, 퀸은 같은 행, 열, 대각선에 있는 상대 기물을 공격할 수 있다. 기물이 체스판 바깥으로 나갈 수는 없다.
체스판 위에 기물들을 이곳저곳 놓아 보던 재헌이는 다음과 같은 3가지 상태를 발견했다.
아래 그림은 왼쪽부터 각각 체크, 체크메이트, 스테일메이트의 한 가지 예를 보여준다.
신이 난 재헌이는 체스판 위에 백색 킹 하나와 흑색 퀸 $K$개를 놓았는데, 이때 백색 킹과 8방향으로 인접한 칸에는 흑색 퀸을 놓지 않았다. 그러고는 이 체스판이 어느 상태에 해당하는지 여러분에게 물어보았다. 재헌이의 질문에 답해보자!
첫째 줄에 체스판의 크기 $N$과 흑색 퀸의 수 $K$가 주어진다. $(3 \le N \le 10^9, 1 \le K \le 100\ 000)$
다음 줄에 백색 킹의 위치 $R, C$가 주어진다. $R$행 $C$열에 백색 킹이 있음을 의미한다. $(1 \le R,C \le N)$
다음 $K$개의 줄에 걸쳐 각 흑색 퀸의 위치 $R_i, C_i$가 주어진다. $i$번째 퀸이 $R_i$행 $C_i$열에 있음을 의미한다. $(1 \le R_i, C_i \le N)$
두 기물의 위치가 중복되는 경우는 없으며, 백색 킹과 8방향으로 인접한 칸에 흑색 퀸이 놓여있는 경우는 주어지지 않는다.
주어진 체스판의 상태가 체크이면 CHECK
를, 체크메이트이면 CHECKMATE
를, 스테일메이트이면 STALEMATE
를, 3가지 상태 중 어느 것에도 속하지 않으면 NONE
을 출력한다.
7 1 4 6 4 3
CHECK
7 3 4 6 3 3 4 3 5 3
CHECKMATE
7 2 4 4 5 2 3 6
STALEMATE
7 1 5 5 4 3
NONE
5 1 5 5 3 4
STALEMATE