Artifact Content
Not logged in

Artifact c308f15b218b41e131ba570f04017a81f9870a20


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;

class CakeParty
{
public:
	string makeMove(vector <int> pieces) 
	{
		// Win iff #{i | pieces[i]==max(pieces)} is odd
		//    --> if #==1      move not to make the opponent winning pos
		//        if #==odd>=3 any move will do. choose the lexic-first one
		//        if #==even   any move leads to lose. choose the lex1st
/*
<<Sprague Grundy Theorem による導出>>

定理のステートメント

    対象となるゲーム
      - 二人ゲーム
      - 二人とも動かせる手の集合は同じ
      - 動かせなくなった方が負け
      - 無限ループしない

    nim
      - サイズ s1, s2, .., sk の山がある
      - どれか一つ山を選んで 1 〜 山サイズ の任意個取り除ける
      - 最後の山を取った方が勝ち(山がなくなって打つ手が無くなった方が負け)

    *n をサイズ n の山が1個だけの nim とする
      - *0 は負け
      - *n は勝ち n>=1

    ゲーム
      - 状態 G から打てる手で遷移する先を G1, ..., Gk とする
        G = {G1, ..., Gk} と書く

    等価
      - 二つのゲームG, Fが等価なことを G ≡ F と書く
        等価というのは勝ち負け一致よりもっと強い。二つのゲームの和を取ると必敗になること
        *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない

    定理
      - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk)
        where mex(S) = min(nat \setminus S)
        帰納的に、全てのゲームはなんらかの *n と等価

適用

  "#max == 1 なら必勝"
       [X,...] = { [X-1,...], [X-2,...], ..., [1, ...], [...] }
     で
       [X-1,...] = { [X-2,...], ..., [1, ...], [...] }
     なので
       [X,...] の nim 値は mex(mex{[X-2,...], ..., [1, ...], [...]}, [X-2,...], ..., [1, ...], [...])
       になるが、これはmex2回がけなので *0 ではない。よって必勝
  "#max == 2 なら必敗"
     どうやっても相手に#max==1で渡ってしまう
  "#max == 3 なら必勝"
     どうやっても相手に#max==2で渡る
  ...

*/
		LL maxI = max_element(pieces.begin(), pieces.end()) - pieces.begin();
		LL maxP = pieces[maxI];
		if( count(pieces.begin(), pieces.end(), maxP) == 1 )
		{
			pieces[maxI] = 0;
			LL second = *max_element(pieces.begin(), pieces.end());

			// if there's odd number of the second largests, make it even
			if( count(pieces.begin(), pieces.end(), second)%2 == 1 )
			{
				stringstream sout;
				sout << "CAKE " << maxI << " PIECES " << (maxP - second);
				return sout.str();
			}
			// otherwise, leave it as is. choose the lex-first move
			else
			{
				LL eat = maxP - second + 1;

				// d : lexicographically first number more than "eat"
				LL d = 1;
				while( !(eat <= d) )
					d *= 10;
				if( d <= maxP ) // if edible
					eat = d;
				stringstream sout;
				sout << "CAKE " << maxI << " PIECES " << eat;
				return sout.str();
			}
		}
		else
		{
			string ans = "Z";
			for(LL i=0; i<pieces.size(); ++i)
				if( pieces[i] == maxP )
				{
					stringstream sout;
					sout << "CAKE " << i << " PIECES 1";
					ans = min(ans, sout.str());
				}
			return ans;
		}
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }

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(); }
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;}

template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
	int pieces_[] = {47};
	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	string RetVal = "CAKE 0 PIECES 47"; 
	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
int Test_(Case_<1>) {
	int pieces_[] = {3,3};
	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	string RetVal = "CAKE 0 PIECES 1"; 
	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
int Test_(Case_<2>) {
	int pieces_[] = {3,5};
	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	string RetVal = "CAKE 1 PIECES 2"; 
	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
int Test_(Case_<3>) {
	int pieces_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1};
	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	string RetVal = "CAKE 0 PIECES 1"; 
	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
int Test_(Case_<4>) {
	int pieces_[] = {3,3,112};
	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	string RetVal = "CAKE 2 PIECES 110"; 
	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
int Test_(Case_<5>) {
	int pieces_[] = {3,3,1};
	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	string RetVal = "CAKE 0 PIECES 1"; 
	return verify_case(RetVal, CakeParty().makeMove(pieces)); }
int Test_(Case_<6>) {
	int pieces_[] = {4,7,4,7,4,7,4,7,47,47,47,47};
	  vector <int> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	string RetVal = "CAKE 10 PIECES 1"; 
	return verify_case(RetVal, CakeParty().makeMove(pieces)); }

template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<>      void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE