[BOJ 12941] 동전 게임
View as PDF
Submit solution
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
Points:
4
Time limit:
2.0s
Memory limit:
512M
Problem types
Allowed languages
Kevin과 Nicky는 새로운 게임을 하고 있다. 게임의 규칙은 다음과 같다.</p>
- i번째의 무더기에 ai개의 동전이 있는 동전 무더기 n개를 갖고 시작한다.
- 두 플레이어는 번갈아 턴을 가진다. (Kevin이 먼저 시작한다.)
- 매 턴, 각 플레이어는 비어있지 않은 한 무더기를 골라, 다음 중 하나를 수행할 수 있다.
- 그 무더기에서 동전 하나를 뺀다.
- (무더기의 동전 개수가 짝수개인 경우만 사용할 수 있다.) 해당 무더기의 동전 개수가 2x개였다고 하자. 이 무더기를 K개의 동전 무더기로 대체한다. 각 동전 무더기는 x개의 동전을 갖는다.
마지막 동전을 가져가는 플레이어가 승리하게 된다. N과 K, ai들이 주어질 때, 두 플레이어가 모두 최적의 플레이를 하는 경우 누가 승리하는지를 출력하시오.
입력 형식
첫 번째 줄에는 N과 K가 주어진다. (1 ≤ n ≤ 100,000, 1 ≤ k ≤ 109)</p>
다음 줄에는 N개의 자연수가 주어진다. (1 ≤ ai ≤ 109)
출력 형식
승리한 사람의 이름을 출력한다. (“Kevin” 또는 “Nicky”)
예제 입력 1
2 1 3 4예제 출력 1
Kevin예제 입력 2
1 2 3예제 출력 2
Nicky
Comments