11868번: 님 게임 2, 11694번: 님 게임 - 스프라그-그런디 정리

11868번: 스프라그-그런디 정리 기본 문제. 님 게임에 대한 기본 이해가 필요하다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int N; cin >> N;
	int nim_sum = 0; //님 합 : 모든 게임판의 상태를 XOR한 값
	for(int i=1; i<=N; i++) 
	{
	    int pi; cin >> pi;
	    nim_sum ^= pi;
	}
    
    //님 합이 0이면 패배 상태, 아니면 승리 상태이다.
    //기저 조건 : 모든 게임판의 상태가 0(님 합이 0)이라면 무조건 패배 상태이다.
    
    //님 합이 0인 상태에서 플레이어가 게임판의 상태를 변경시킨다면, 님 합이 0이 아니게 된다.
    //즉 패배 상태 이후는 무조건 승리 상태이다.
    
    //님 합이 0이 아닌 상태에서, 님 합을 0으로 만드는 경우는 무조건 존재한다.
    //XOR 연산 특성상 님 합의 최고 비트에 대응되는 게임판은 무조건 존재한다.
    //그러한 게임판의 상태는 님 합보다 크기 때문에, 해당 게임판의 상태를 조작해 님 합을 0으로 만들 수 있다.
    //즉 승리 상태에서 패배 상태로 갈 수 있는 경우는 무조건 존재한다.
    
    //패배 상태 이후는 무조건 승리 상태이고, 승리 상태에서는 패배 상태로 갈 수 있는 경우가 반드시 존재한다.
    //따라서 님 합이 0이면 패배, 아니면 승리한다.
	
	if(nim_sum == 0) cout << "cubelover";
	else cout << "koosaga";
}

 

11694번: 미제르 님 게임

님 합이 0이 아닐 때 님 게임을 진행해 보자. 님 게임은 님 합을 0으로 만들기 위해 특정한 돌 더미의 돌을 계속 없애므로, 언젠가는 각 돌 더미에 쌓인 돌의 최대 개수가 1일 때가 된다. 그런데 님 합이 0이 아니면 무조건 님 합을 0으로 만들 수 있으므로, 돌의 최대 개수가 1인 돌 더미의 개수는 무조건 짝수가 될 수밖에 없다. 이러한 상태는 패배 상태이므로, 님 합이 0이 아니라면 대개의 경우 첫 번째 플레이어가 승리할 수 밖에 없다. 하지만 모든 돌 더미에 쌓인 돌의 최대 개수가 1인데, 돌 더미의 개수가 홀수라면 첫 번째 플레이어가 패배하게 된다. 미제르 님 게임에서의 유일한 예외 조건이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int N; cin >> N;
	int nim_sum = 0;
	bool isAllOne = true;
	for(int i=1; i<=N; i++) 
	{
	    int pi; cin >> pi;
	    nim_sum ^= pi;
	    if(pi != 1) isAllOne = false;
	}
	
	if(isAllOne)
	{
	    if(N % 2) cout << "cubelover";
	    else cout << "koosaga";
	}
	else
	{
	    if(nim_sum) cout << "koosaga";
	    else cout << "cubelover";
	}
}