#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