README.md

[Gold IV] 팰린드롬 게임 - 24553

문제 링크

성능 요약

메모리: 2020 KB, 시간: 44 ms

분류

애드 혹, 게임 이론

문제 설명

상윤이와 승우는 통산전적 1000전 500승 500패, 영혼의 라이벌이다.

이들 중 누가 더 게임을 잘하는지 구별하기 위해 마지막 게임 한 판을 하기로 했다.

게임의 룰은 다음과 같다.

1.  N$N$개의 돌이 쌓여있는 돌 무더기에서 게임을 진행한다.
2. 상윤이가 게임을 먼저 시작한다. 그 후에 승우, 상윤이 번갈아가면서 게임을 진행한다.
3. 자신의 차례가 오면, 돌 무더기에서 돌을 x$x$개 가져오는 행동을 할 수 있다. 이 때, x$x$는 팰린드롬 수여야 한다.
4. 자신의 차례에 가져올 돌이 없다면 그 사람은 패배한다.

팰린드롬 수란 3$3$, 11$11$, 929$929$ 와 같이 뒤집어도 같은 수가 나오는 양의 정수를 의미한다. 010$010$ 와 같이 의미 없는 0$0$이 앞에 있는 경우는 포함하지 않는다.

상윤이와 승우 모두 1000판의 게임을 해온 고수들이라 항상 최선의 수만을 둔다.

돌의 개수 N$N$이 주어졌을 때, 누가 이기는지 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T$T$가 주어진다. (1≤T≤1000$1 \le T \le 1\,000$)

둘째 줄부터 T$T$개의 줄에 걸쳐, 돌 무더기에 쌓여 있는 돌의 개수 N$N$이 주어진다. (1≤N≤1018$1 \le N \le 10^{18}$)

출력

각 게임에서 상윤이가 이긴다면 0, 승우가 이긴다면 1을 출력한다.