구슬 게임
면접 대비시간 제한2초메모리 제한512 MB
각 대리석을 와이토프 게임의 두 더미로 보고 스프라그-그런디 값을 계산해 선공 승리 여부를 판단합니다.
문제
쿠비코니아에서 구슬을 화폐로 쓰는 일은 그다지 성공적이지 못했다. 친구들의 구슬을 훔친 뒤 사과하려는 마음에서, 황제는 친구들을 모두 궁전으로 초대해 게임을 하기로 했다.
게임에 구슬을 쓰는 것은 당연하다. 이제 황제는 그렇게 많은 구슬을 쓸 곳을 찾아야 한다. N개의 구슬이 커다란 판 위에 흩어져 있고, 판의 행은 0부터 L까지, 열은 0부터 C까지 번호가 붙어 있다. 플레이어들은 차례로 턴을 가지며, 각 턴에서 자기 차례인 플레이어는 구슬 하나를 골라 움직여야 한다. 구슬을 (0, 0) 위치로 옮긴 플레이어가 이긴다. 게임을 재미있게 만들기 위해 이동에는 제한이 있다. 그렇지 않으면 첫 플레이어가 항상 구슬을 (0, 0)으로 옮겨 이기기 때문이다. 한 번의 이동은 0보다 큰 정수 u와 구슬 하나를 고르는 것으로 이루어지며, 구슬의 위치를 (l, c)라 할 때 다음 위치 중 하나로 옮긴다. 단, 판을 벗어나지 않아야 한다.
- (l − u, c);
- (l, c − u); 또는
- (l − u, c − u).
여러 구슬이 판 위의 같은 위치에 있을 수 있다.
황제는 지는 것을 좋아하지 않으므로, 어떤 게임에 참가해야 할지 결정하도록 도와야 한다. 당연히 황제는 항상 첫 턴을 가진다. 모두가 최적으로 플레이한다고 가정할 때, 프로그램은 판 위 구슬의 초기 배치를 분석하여 황제가 게임을 이길 수 있는지 없는지를 알려야 한다.
입력
첫째 줄에는 정수 N (1 ≤ N ≤ 1000)이 주어진다. 다음 N개의 줄 각각에는 두 정수 li와 ci가 주어지며, i번째 구슬이 판의 어느 행과 열에 있는지를 나타낸다 (1 ≤ li, ci ≤ 100).
출력
프로그램은 황제가 게임을 이길 수 있으면 Y, 그렇지 않으면 N을 한 줄에 출력한다.