[Python] 16887번 루트 님 게임

 

 

https://www.acmicpc.net/problem/16887

16887번: 루트 님 게임

---

 

23/04/06

 

 

스프라그-그런디 문제로, 사실 스프라그-그런디 정리를 곁들인 수학 문제라고 봐도 무방한 문제다.

 

그런디 수를 구하는 경계가 조금 구하기 귀찮기 때문에 난도가 높은 것이라고 생각한다.

 

하지만 개인적으로 플레티넘 1을 받을 정도의 난이도는 아니라고 생각하는 문제다.

---

 

문제 접근 방식:

 

 

문제에서 주어진 것 처럼 그대로 구현하면 당연히 시간 초과가 날 것이다.

 

이는 직접 해보면 잘 알 것이다..

 

그러면 어떻게 구할 건데?가 문제가 될 것이다.

 

한 $1000$개까지 직접 코드를 짜서 돌려보면, 중복되는 그런디 수가 "매우" 많음을 확인할 수 있다.

 

 

 

아래는 구하는 과정을 나타낸 코드이다.

 

def mex(S):
    for num, i in zip(sorted(S), range(len(S))):
       if num != i:
           return i
    return len(S)
grundy = [0, 0, 0]
for x in range(3, 1000):
    S = set()
    for y in range(x):
        if x <= y**4 <= x**2:
            S.add(grundy[y])
    grundy.append(mex(S))

 

그러면 우린 "일정 범위"의 그런디 수는 모두 같다는 사실을 $ x^{1/4} \leq y \leq x^{1/2} $라는 식을 통해 직관적으로 알 수 있다.

 

 

그러면 실제 범위는 어떻게 구할까?

 

먼저, $1000$까지의 범위는 이전에 구했으므로, 그 이후의 범위를 알아봐야 한다.

 

 

문제를 보면, $x$가 주어지면, $x$의 네제곱근보다는 크거나 같고, $x$의 제곱근보다는 작거나 같은 $y$로 돌 더미의 개수를 변화시킬 수 있다고 했다.

 

 

$1000$까지 구한 값에 의하면, $82$ 이후에는 그런디 수의 값이 전부 $0$이 나오는 것을 확인할 수 있다.

 

그런디 수를 구할 때에는 $mex$함수를 사용하므로, $82$의 상태로 갈 수 있을 때부터 $0$인 상태로 갈 수 있는 것이므로, 적어도 그때부터는 그런디 수가 $0$이 아닐 것이다.

 

$82$인 상태로 갈 수 있는 경계는 $x$의 값이 $82^2 = 6724$일 때이다.

 

이때 $x^{1/4} = 9.055$정도 되므로, $6724$이후에는 $mex(1, 2, 0) = 3$이 그런디 수가 될 것이다.

 

 

그러다가 그런디 수가 $1$인 범위($[4, 15]$)를 갈 수 없어서, $mex$값이 $1$이 나오는 경계가 생길 것이다.

 

그 경계는 $x = 15^4 + 1 = 50656$이다.

 

이때, $x^{1/2} = 225.06$정도 되므로, $50626$이후부터는 $mex(0, 3) = 1$이 나오게 될 것이다.

 

 

이후 $x$가 점점 커지다보면 그런디 수가 $1$인 범위($[50626, )$), 즉, $50626$을 포함하는 경계가 나올 수 있는데, 그러면 $mex$값이 $mex(0, 3, 1) = 2$가 나온다.

 

그 경계는 $50626^2 = 2562991876$으로, 그 이후부터는 $2$가 나온다고 이야기할 수 있다.

 

 

이렇듯 손으로 직접 계산하면 금방 구할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 16887번 루트 님 게임
# 게임 이론, 스프라그-그런디 정리
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().rstrip().split()))

##def mex(S):
##    for num, i in zip(sorted(S), range(len(S))):
##       if num != i:
##           return i
##    return len(S)
##grundy = [0, 0, 0]
##for x in range(3, 1000):
##    S = set()
##    for y in range(x):
##        if x <= y**4 <= x**2:
##            S.add(grundy[y])
##    grundy.append(mex(S))

total = 0
for a in A:
    if a < 4:
        total ^= 0
    elif 4 <= a <= 15:
        total ^= 1
    elif 16 <= a <= 81:
        total ^= 2
    elif 82 <= a <= 6723:
        total ^= 0
    elif 6724 <= a <= 50625:
        total ^= 3
    elif 50626 <= a <= 2562991875:
        total ^= 1
    else:
        total ^= 2
if total == 0:
    print('cubelover')
else:
    print('koosaga')