[백준 C++] 11872 님 게임 나누기

문제

koosaga와 cubelover가 "님 게임 나누기 버전"을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 다음과 같이 2가지 중 하나를 선택할 수 있다.

1. 일반적인 님 게임과 똑같이 돌 더미 하나를 선택해 돌을 하나 이상 제거한다.
2. 돌이 적어도 2개 있는 돌 더미 하나를 선택한 다음, 두 개의 비어있지 않은 돌 더미로 나눈다. (돌은 제거할 수 없다)
   전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다.

게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.

입력

첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 100)이 주어진다.

둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 Pi (1 ≤ Pi ≤ 2×109)가 주어진다.

출력

koosaga가 이기는 경우에는 'koosaga'를, cubelover가 이기는 경우에는 'cubelover'를 출력한다.

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

풀이

돌무더기를 나눈다는것에대한 의미를 깨달아야한다.
이미 우리는 여러 돌무더기가있을때 전체 그런디수를
모든 돌무더기수를 XOR연산한 결과로 구했었다.

따라서 역으로, 돌무더기를 나눈다면 나뉜 두 돌무더기간의 XOR연산으로 그런디집합을 구해보면 되는것이다.
보라색으로 표기한곳이 실제 *n의 그런디수값 이다.
이를 구하는과정에서 돌무더기를 나눌 수 있는 경우의수를 모두 구한뒤,
그 값을 보라색으로 표기한 실제 그런디수값으로 치환하여 계산하여 집합을 만든뒤,
그런디수의 정의에의해 이 집합에없는 최소정수를 그런디수값으로 구하였다.
자세한 설명은 그림에 모두 나와있다.

여기까지 구한다면 0부터 그런디수값이 0,1,2,4,3,5,6,8,7,9.''' 즉, 4k, 4k-1일때 마다 그런디수값이 달라지는 규칙을 가지고있다.

이를 코드로 나타내면 아래와 같다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::stack; using std::queue;
using std::deque; using std::string; using std::pair;
using std::sort;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, char> pic;
typedef pair<char, int> pci;

ll g;
void init();
void func();
void init() {
    int n;
    scanf("%d", &n);
    while (n--) {
        ll p;
        scanf("%lld", &p);
        if (p % 4 == 0)
            g ^= p - 1;
        else if (p % 4 == 3)
            g ^= p + 1;
        else
            g ^= p;
    }
}

void func() {
    !g ? printf("cubelover") : printf("koosaga");
}

int main(void) {
    init();
    func();


    return 0;
}