[TIOJ] 1087. [Interactive] 取石頭(一)

題目連結:http://tioj.infor.org/problems/1087

---

經典的NIM題，可以用SG Value發現本題先手必勝，但要怎麼玩呢??，不難發現若且為若對方的盤面SG值為0他就輸了，因此我只要想辦法構造讓對方的三堆石頭xor起來是0，特別的是當剩兩堆且一堆為一時，顯然我們只要把那堆不為0的拿走就好了，而剩一堆時顯然把那堆拿到剩一就好了，所以記得特判一下

#include "lib1087.h"

int stone[] = {10,15,20};
inline bool all0();
inline bool only1(int);

int main(){
	Initialize();
	while(!all0()){
		for(int i=0;i<3;i++){
			int cnt,pile;
			if(stone[0]+stone[1]==1){
				Take_Stone(3, stone[2], &pile, &cnt);
				stone[2]=0;
				stone[pile-1]-=cnt;
				break;
			}else if(stone[0]+stone[2]==1){
				Take_Stone(2, stone[1], &pile, &cnt);
				stone[1]=0;
				stone[pile-1]-=cnt;
				break;
			}else if(stone[1]+stone[2]==1){
				Take_Stone(1, stone[0], &pile, &cnt);
				stone[0]=0;
				stone[pile-1]-=cnt;
				break;
			}
			if(only1(i)){
				while(stone[i]==1){i++;--i;}
				Take_Stone(i+1, stone[i]-1, &pile, &cnt);
				stone[i]=1;
				stone[pile-1]-=cnt;
				break;
			}
			int xx=0;
			for(int j=0;j<3;j++)if(i!=j) xx^=stone[j];
			if(xx<=stone[i]){
				Take_Stone(i+1, stone[i]-xx, &pile, &cnt);
				stone[i]=xx;
				stone[pile-1]-=cnt;
				break;
			}
		}
	}
	return 0;
}

inline bool all0(){
	for(int i=0;i<3;i++)if(stone[i]!=0)return 0;
	return 1;
}
inline bool only1(int x){
	for(int i=0;i<3;i++)if(i!=x&&stone[i]!=0)return 0;
	return 1;
}