어제 종료된 Semi-Game Cup의 제일 첫 문제입니다.
열심히 노느라 참가를 하지는 못했지만, 문제가 공개된 후에 풀어보니 A번인 이 문제만큼은 난이도가 평이하고 재밌더군요.
문제에서 제시된 게임은 각 플레이어가 다음과 같은 행동을 취할 수 있는 님게임과 일치합니다.
- 돌을 임의의 개수만큼 가져온다.
- 해당 무더기에서 가져온 돌 중 일부를 다시 쌓는다.
이 때, 먼저 모든 무더기의 돌의 개수를 xor한 값이 0이 되게 한 플레이어는 상대방이 돌을 쌓던 돌을 가져가던 다시금 돌의 개수를 xor한 값이 0이 되게 할 수 있습니다.
상대가 계속 돌을 다시 쌓더라도, 다시 쌓은 만큼 돌을 가져가면 돌무더기의 xor 값은 일정하게 유지할 수 있고, 상대가 가진 돌의 개수는 점점 줄어드므로 게임이 무한히 지속될 수는 없습니다.
즉슨 이 문제도 스프라그 그런디 정리를 적용하여 완벽히 해결 가능하다는 뜻이지요.
이를 코드로 옮기면 다음과 같습니다.
#include<bits/stdc++.h>
using namespace std;
//결과를 인덱스로 출력하기 위함
string res[]={"Blackking","Whiteking"};
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
int n,r=0;
cin>>n;
//돌무더기에서 돌을 가져오는 게임으로 바꿔 생각하여, 입력-2를 모두 xor
while(n--){
int x;
cin>>x;
x-=2;
r^=x;
}
char c;
cin>>c;
c=(c=='W');//선공의 인덱스
if(!r)c^=1;//xor 결과가 0이라면 후공 필승
cout<<res[c];
}