테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 동전 게임 ======

===== 풀이 =====
  * 동전이 n개 있을때의 그런디수를 g(n)라고 하자.
  * 동전 2x개를 동전 x개짜리 무더기 K개로 바꾸는 행동을 할때를 생각하면, 동전 n개짜리 무더기 K개의 그런디수는 g(x)^g(x)^...^g(x) 이니까, K가 짝수이면 0, K가 홀수이면 g(x)가 된다. 
  * 이제 그런디수를 계산하는 것은 어렵지 않다. DP로 구해도 O(n)에 계산가능하지만, n이 10^9로 꽤 크니까 규칙성을 찾아보자.
  * K가 짝수이면 심플하다. 손으로 조금 써보면 g(0)=0, g(1)=1, g(2)=2 이고, 2보다 큰 수에 대해서는 g(2m)=1, g(2m+1)=0 인것을 알수 있다. 짝수일때에 1을 줄이든, K개로 나누든 모두 그런디수를 0으로 만드니까, 짝수일때의 그런디수는 1이다.
  * K가 홀수일때는 살짝 복잡한데, 우선 0~4까지의 그런디수는 0,1,0,1,4이다. 5이상일때는, 홀수의 그런디수는 0이다. 짝수의 그런디수 g(2m)은 g(m)이 0 또는 2이면 1이 되고, g(m)이 1이면 2가 된다.
    * 이 방식으로 짝수일때의 그런디수를 구하는것은 n/(2^k)가 홀수일때부터 g(n/(2^k)), ..., g(n/4), g(n/2), g(n) 을 다 구해서 계산해도 O(logn)에 구할수 있기는 하다. 하지만 식을 좀 더 정리해서 더 쉽게 구할수도 있다, n을 2^k*(2m+1) 이라고 표현될때, g(n)은 k가 짝수이면 2, k가 홀수이면 1이 된다. 이때, 예외는 n=2^k*3 일때인데, 이경우에는 k가 짝수일때 1, k가 홀수일때 2가 된다. 예외가 생기는 이유는 5이상의 홀수들은 그런디수가 모두 0이지만, 3의 그런디수만 1이기 때문이다.
    * 저 공식을 비트연산을 이용해서 구하면 O(1)에 그런디수 계산이 가능하다.
  * 결국 K와 n에 관계 없이, 언제나 g(n)을 O(1)에 구할수 있다. 모든 a_i에대해서 그런디수를 구하고 xor합을 계산하면 끝이므로, 시간복잡도는 O({파일의 갯수})이다


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 12941. 동전 게임".

- Problem link: https://www.acmicpc.net/problem/12941
- Solution link: http://www.teferi.net/ps/problems/boj/12941

Tags: [game theory]
"""

import functools
import operator


def grundy_even_k(n):
    if n <= 2:
        return n
    return (n + 1) % 2


def grundy_odd_k(n):
    if n <= 3:
        return n % 2
    if n % 2 == 1:
        return 0
    power_2 = (n & (-n)).bit_length() - 1
    if n >> power_2 == 3:
        return power_2 % 2 + 1
    return (power_2 + 1) % 2 + 1


def main():
    N, K = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    a = [int(x) for x in input().split()]

    compute_grundy = grundy_odd_k if K % 2 == 1 else grundy_even_k
    grundy = functools.reduce(operator.xor, (compute_grundy(x) for x in a))

    print('Kevin' if grundy > 0 else 'Nicky')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_2}}