소 자릿수 게임
면접 대비시간 제한1초메모리 제한128 MB
각 시작 수에서 두 사람이 번갈아 그 수의 가장 큰 자릿수나 가장 작은 0이 아닌 자릿수를 빼며 0을 만든 사람이 이긴다. 선공의 승패를 판정한다.
문제
베시(Bessie)가 농부 존(Farmer John)을 상대로 숫자 게임을 합니다. 베시가 이길 수 있도록 도와주세요.
각 게임은 정수 ()에서 시작합니다. 베시가 먼저 두고, 이후 두 사람이 번갈아 차례를 갖습니다. 각 차례에 현재 플레이어는 현재 수의 자리 숫자 중 가장 큰 숫자, 또는 이 아닌 가장 작은 숫자를 골라 현재 수에서 뺍니다. 예를 들어 에서는 또는 를 뺄 수 있어 또는 이 됩니다. 수가 이 될 때까지 게임이 계속되며, 마지막으로 수를 움직여 을 만든 플레이어가 이깁니다.
베시와 농부 존은 번의 게임 ()을 합니다. 두 사람 모두 최적으로 플레이한다고 할 때(즉, 자신의 승리를 보장하는 수가 있으면 반드시 그 수를 둡니다), 각 게임에서 누가 이기는지 판정하세요.
예를 들어 인 경우를 봅시다. 베시가 먼저 을 빼서 을 만듭니다. 농부 존은 어쩔 수 없이 을 빼서 를 만듭니다. 베시가 를 빼서 을 만들며 이깁니다.
입력
- 첫째 줄: 정수 .
- 번째 줄: 번째 줄에는 게임 의 시작 수 가 하나씩 주어집니다.
출력
- 번째 줄: 번째 줄에 베시가 게임 에서 이기면 "YES", 그렇지 않으면 "NO"를 출력합니다.
힌트
시작 수가 이면 베시는 를 빼서 곧바로 이깁니다. 시작 수가 이면 베시는 (은 뺄 수 없으므로) 을 빼야 하고 가 남습니다. 그러면 농부 존이 를 빼서 이기므로 베시는 집니다.