시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 179 | 91 | 68 | 47.887% |
구사과와 큐브러버는 나누기 게임을 하려고 한다. 이 게임은 돌이 N개 포함되어 있는 돌 더미 1개에서 시작한다. 두 사람은 턴을 번갈아 가지며, 구사과가 턴을 먼저 갖는다. 각 턴마다 다음을 할 수 있다.
더 이상 나눌 돌 더미가 없는 사람이 게임에서 진다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 누가 이기는지 구하는 프로그램을 작성하시오.
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다.
구사과가 이기는 경우에는 첫 턴에서 구사과가 만든 돌 더미의 개수 k를 출력한다. 가능한 k가 여러가지인 경우에는 가장 작은 값을 출력한다. 큐브러버가 이기는 경우에는 -1을 출력한다.
3
2
6
-1
100
8