4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class CakeParty
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	string makeMove(vector <int> pieces)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		// Win iff #{i | pieces[i]==max(pieces)} is odd
4fd800b3a8 2011-02-23        kinaba: 		//    --> if #==1      move not to make the opponent winning pos
4fd800b3a8 2011-02-23        kinaba: 		//        if #==odd>=3 any move will do. choose the lexic-first one
4fd800b3a8 2011-02-23        kinaba: 		//        if #==even   any move leads to lose. choose the lex1st
4fd800b3a8 2011-02-23        kinaba: /*
4fd800b3a8 2011-02-23        kinaba: <<Sprague Grundy Theorem による導出>>
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 定理のステートメント
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba:     対象となるゲーム
4fd800b3a8 2011-02-23        kinaba:       - 二人ゲーム
4fd800b3a8 2011-02-23        kinaba:       - 二人とも動かせる手の集合は同じ
4fd800b3a8 2011-02-23        kinaba:       - 動かせなくなった方が負け
4fd800b3a8 2011-02-23        kinaba:       - 無限ループしない
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba:     nim
4fd800b3a8 2011-02-23        kinaba:       - サイズ s1, s2, .., sk の山がある
4fd800b3a8 2011-02-23        kinaba:       - どれか一つ山を選んで 1 〜 山サイズ の任意個取り除ける
4fd800b3a8 2011-02-23        kinaba:       - 最後の山を取った方が勝ち（山がなくなって打つ手が無くなった方が負け）
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba:     *n をサイズ n の山が1個だけの nim とする
4fd800b3a8 2011-02-23        kinaba:       - *0 は負け
4fd800b3a8 2011-02-23        kinaba:       - *n は勝ち n>=1
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba:     ゲーム
4fd800b3a8 2011-02-23        kinaba:       - 状態 G から打てる手で遷移する先を G1, ..., Gk とする
4fd800b3a8 2011-02-23        kinaba:         G = {G1, ..., Gk} と書く
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba:     等価
4fd800b3a8 2011-02-23        kinaba:       - 二つのゲームG, Fが等価なことを G ≡ F と書く
4fd800b3a8 2011-02-23        kinaba:         等価というのは勝ち負け一致よりもっと強い。二つのゲームの和を取ると必敗になること
4fd800b3a8 2011-02-23        kinaba:         *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba:     定理
4fd800b3a8 2011-02-23        kinaba:       - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk)
4fd800b3a8 2011-02-23        kinaba:         where mex(S) = min(nat \setminus S)
4fd800b3a8 2011-02-23        kinaba:         帰納的に、全てのゲームはなんらかの *n と等価
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 適用
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba:   "#max == 1 なら必勝"
4fd800b3a8 2011-02-23        kinaba:        [X,...] = { [X-1,...], [X-2,...], ..., [1, ...], [...] }
4fd800b3a8 2011-02-23        kinaba:      で
4fd800b3a8 2011-02-23        kinaba:        [X-1,...] = { [X-2,...], ..., [1, ...], [...] }
4fd800b3a8 2011-02-23        kinaba:      なので
4fd800b3a8 2011-02-23        kinaba:        [X,...] の nim 値は mex(mex{[X-2,...], ..., [1, ...], [...]}, [X-2,...], ..., [1, ...], [...])
4fd800b3a8 2011-02-23        kinaba:        になるが、これはmex2回がけなので *0 ではない。よって必勝
4fd800b3a8 2011-02-23        kinaba:   "#max == 2 なら必敗"
4fd800b3a8 2011-02-23        kinaba:      どうやっても相手に#max==1で渡ってしまう
4fd800b3a8 2011-02-23        kinaba:   "#max == 3 なら必勝"
4fd800b3a8 2011-02-23        kinaba:      どうやっても相手に#max==2で渡る
4fd800b3a8 2011-02-23        kinaba:   ...
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: */
4fd800b3a8 2011-02-23        kinaba: 		LL maxI = max_element(pieces.begin(), pieces.end()) - pieces.begin();
4fd800b3a8 2011-02-23        kinaba: 		LL maxP = pieces[maxI];
4fd800b3a8 2011-02-23        kinaba: 		if( count(pieces.begin(), pieces.end(), maxP) == 1 )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			pieces[maxI] = 0;
4fd800b3a8 2011-02-23        kinaba: 			LL second = *max_element(pieces.begin(), pieces.end());
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			// if there's odd number of the second largests, make it even
4fd800b3a8 2011-02-23        kinaba: 			if( count(pieces.begin(), pieces.end(), second)%2 == 1 )
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				stringstream sout;
4fd800b3a8 2011-02-23        kinaba: 				sout << "CAKE " << maxI << " PIECES " << (maxP - second);
4fd800b3a8 2011-02-23        kinaba: 				return sout.str();
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 			// otherwise, leave it as is. choose the lex-first move
4fd800b3a8 2011-02-23        kinaba: 			else
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				LL eat = maxP - second + 1;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 				// d : lexicographically first number more than "eat"
4fd800b3a8 2011-02-23        kinaba: 				LL d = 1;
4fd800b3a8 2011-02-23        kinaba: 				while( !(eat <= d) )
4fd800b3a8 2011-02-23        kinaba: 					d *= 10;
4fd800b3a8 2011-02-23        kinaba: 				if( d <= maxP ) // if edible
4fd800b3a8 2011-02-23        kinaba: 					eat = d;
4fd800b3a8 2011-02-23        kinaba: 				stringstream sout;
4fd800b3a8 2011-02-23        kinaba: 				sout << "CAKE " << maxI << " PIECES " << eat;
4fd800b3a8 2011-02-23        kinaba: 				return sout.str();
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		else
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			string ans = "Z";
4fd800b3a8 2011-02-23        kinaba: 			for(LL i=0; i<pieces.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 				if( pieces[i] == maxP )
4fd800b3a8 2011-02-23        kinaba: 				{
4fd800b3a8 2011-02-23        kinaba: 					stringstream sout;
4fd800b3a8 2011-02-23        kinaba: 					sout << "CAKE " << i << " PIECES 1";
4fd800b3a8 2011-02-23        kinaba: 					ans = min(ans, sout.str());
4fd800b3a8 2011-02-23        kinaba: 				}
4fd800b3a8 2011-02-23        kinaba: 			return ans;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: int verify_case(const string &Expected, const string &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> struct Case_ { Case_(){start_time=clock();} };
4fd800b3a8 2011-02-23        kinaba: char Test_(...);
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<0>) {
4fd800b3a8 2011-02-23        kinaba: 	int pieces_[] = {47};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal = "CAKE 0 PIECES 47";
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<1>) {
4fd800b3a8 2011-02-23        kinaba: 	int pieces_[] = {3,3};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal = "CAKE 0 PIECES 1";
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<2>) {
4fd800b3a8 2011-02-23        kinaba: 	int pieces_[] = {3,5};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal = "CAKE 1 PIECES 2";
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<3>) {
4fd800b3a8 2011-02-23        kinaba: 	int pieces_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal = "CAKE 0 PIECES 1";
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<4>) {
4fd800b3a8 2011-02-23        kinaba: 	int pieces_[] = {3,3,112};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal = "CAKE 2 PIECES 110";
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<5>) {
4fd800b3a8 2011-02-23        kinaba: 	int pieces_[] = {3,3,1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal = "CAKE 0 PIECES 1";
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<6>) {
4fd800b3a8 2011-02-23        kinaba: 	int pieces_[] = {4,7,4,7,4,7,4,7,47,47,47,47};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal = "CAKE 10 PIECES 1";
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
4fd800b3a8 2011-02-23        kinaba: template<>      void Run_<-1>() {}
4fd800b3a8 2011-02-23        kinaba: int main() { Run_<0>(); }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE
4fd800b3a8 2011-02-23        kinaba: