問題
http://community.topcoder.com/stat?c=problem_statement&pm=12474&rd=15494
２人のプレイヤーが交互に行うゲーム。
それぞれ正の整数が与えられる。
各ターンにて、プレイヤーはその数字を１０で割るか、逆にすることができる。
このとき、最初のプレイヤーの数字を２人目のプレイヤーの数字に一致させることができるかどうかを答える。
ターン数は最大で１０００。
解き方
２人目のプレイヤーの数字にすることができれば、
その後の操作は全て一緒にできるので答えは必ずＹＥＳになる。
仮に一緒にできなければ、２人目のプレイヤーは数字をひっくり返し続けてればよいのでＮＯとなる。
待ち伏せる場合、２人目のプレイヤーが逆になるのを待ち伏せる場合は逆にできないので例外、と考えがちだが、逆の数字にできるということは最初の数字にもできるということなので問題ない。
Challenge
2人の操作で１ターンではなく、１人のプレイヤーの操作が終われば1ターンで、
そこで判定できることを見逃してしまった。問題文の理解ミスです。
sprintfはchar型で使うのですが、stringをchar変換しようとしたらうまくいかなかったです。そのままchar型を宣言して使いました。
コード
class TheNumberGame {
public:
string determineOutcome(int A, int B) {
bool win=false;
char tx[15],ty[15];
sprintf(tx,"%d",A);
sprintf(ty,"%d",B);
string x=tx,y=ty;
if(x.find(y)!=string::npos)win=true;
reverse(y.begin(),y.end());
if(x.find(y)!=string::npos)win=true;
return win ? "Manao wins" :"Manao loses";
}
};
public:
string determineOutcome(int A, int B) {
bool win=false;
char tx[15],ty[15];
sprintf(tx,"%d",A);
sprintf(ty,"%d",B);
string x=tx,y=ty;
if(x.find(y)!=string::npos)win=true;
reverse(y.begin(),y.end());
if(x.find(y)!=string::npos)win=true;
return win ? "Manao wins" :"Manao loses";
}
};
Share this
Related Posts
SRM 559 DIV1 Easy - HyperKnight
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12201&rd=15181
解き方
サンプルを表に書いて見ると、各動ける数ごとに- SRM 386 DIV1 Easy - CandidateKeys
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8444&rd=11120
解き方
ビット列ですべての組み合わせについて調べれば良
- SRM 398 DIV1 Easy - CountExpressions
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8157&rd=12170
解き方
O（4! * 3^3）なので全探索可能。
ｘ
- SRM 619 DIV1 Easy - SplitStoneGame (××)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13113&rd=15852
・積み重ねられた石の山が複数存在する。
・それぞれの山につい