Informatica Online Judge

  공 가져가기 I (Large) [0703 / 02BF]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 50   Total Tried : 89


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

경곽이는 또 공놀이를 하고 있다.

여러 개의 공이 담긴 바구니에서 두 명이 번갈아서 한개 이상의 공을 가져가는 게임이 있다. 먼저 공을 가져가는 사람을 A라하고 A의 상대편을 B라고 할 때 이 게임의 규칙은 다음과 같다.

(규칙1) 맨 처음 게임을 시작할 때 A는 바구니에 담긴 모든 공을 가져가는 것을 제외하고는 임의의 개수의 공을 가져갈 수 있다.
(규칙2) 처음에 A가 공을 가져간 다음부터는 한개 이상의 공을 가져가며 상대편이 바로 전에 가져간 개수의 2배 이하로만 공을 가져가야 한다.
(규칙3) 마지막으로 바구니에서 공을 가져간 사람이 이긴다.

예를 들어, 게임 시작 전에 4개의 공이 바구니에 있다고 하자. A가 처음 가져갈 수 있는 공의 개수는 1개 이상 3개 이하이다. 각각의 경우에 두 사람이 최선을 다한다면 다음과 같은 결과가 된다.

(1) A가 1개를 가져가면 B는 2개 이하만 가져갈 수 있다. B가 1개를 가져가는 경우와 2개를 가져가는 경우 모두에 대해 A는 나머지를 다 가져갈 수 있으므로 A가 이긴다.
(2) A가 2개를 가져가면 B가 남은 2개를 가져가서 B가 이긴다.
(3) A가 3개를 가져가면 B가 남은 1개를 가져가서 B가 이긴다.

위의 경우를 보면 처음에 4개의 공이 있는 경우에는 A가 1개의 공을 가져가면 다음에 B가 어떻게 공을 가져가더라도 A가 이길 수 있는 방법이 있다는 것을 알 수 있다. 한편, 처음에 2개의 공이 있으면 A는 1개를 가져갈 수밖에 없으므로 B가 항상 이기게 된다.

문제는 공의 개수가 주어졌을 때 A가 처음에 몇 개의 공을 가져가면 B가 다음 차례들에서 어떻게 공을 가져가더라도 A가 이길 수 있는 방법이 있느냐하는 것이다.

Input

첫 번째 줄에는 공의 개수 n이 있다.

입력값의 정의역은 다음과 같다.

2<= n <=1 000 000

Output

첫 줄에 게임을 이기기 위해 A가 처음에 가져가야 하는 공의 개수를 출력한다. 답이 여러 개인 경우는 그 중에 가장 작은 값을 출력한다. 만약 A가 어떻게 가져가더라도 항상 B가 이길 수 있는 방법이 있으면 첫 줄에 -1을 출력한다.

IO Example

입력
4
출력
1

출제 및 Data제작 : Seaguy

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]