공가져가기 게임 > 문제은행



문제은행

1507 : 공가져가기 게임

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 5 회    시도횟수: 16 회   



두 명이 번갈아서 한 개 이상의 공을 가져가는 게임이 있다. 먼저 공을 가져가는 사람을 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가 공 두 개를 가져가면 B가 남은 두 개의 공을 가져가 B가 이긴다.
(3) A가 공 3개를 가져가면 B가 남은 공을 가져가 B가 이긴다.

 

위의 경우를 보면 공 4개를 먼저 가져가기의 경우에는 A가 공 1개를 가져가면 다음에 B가 공을 몇 개 가져가더라도 A가 이길 수 있는 방법이 있다는 것을 알 수 있다. 한편, 공 2개를 먼저 가져가는 경우에는 A는 공을 1개 가져갈 수밖에 없으므로 B가 항상 이긴다. 문제는 먼저 공의 수가 주어졌을 때 A가 항상 이길 수 있는 방법이 있느냐하는 것이다.




첫 줄에 게임의 회수 N이 주어진다.
두 번째 줄부터는 먼저 부르기의 수 M(M≤100,000)이 주어진다.



수 N에 대한 처음에 부를 수의 개수를 출력한다.
항상 이길 수 없는 경우에는 -1을 출력한다.


3
4
10
13
1
2
-1






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.