SRM 574 Div1 Easy TheNumberGame
問題
プレーヤーが二人いて各々が数字をひとつ持っている。この数字は10進数表記で0を含んでいない。1ターンごとに交互の順番で以下の2つの操作のうち好きな方を選んで行う。
- 数字を逆順にする
- 数字を10で割る
先方のプレーヤーが1000ターン以内に後方の持つ数字と同じにできれば先方の勝ちになる。両者が最適に勝負をした時、先方は勝つことができるか。
やりかた
2つの数字は文字列として持っておくとわかりやすい。
後方の文字列が先方の文字列に含まれていない場合、後方が毎回逆順にする操作を行えば、数字が一致することは絶対にない。しかし含まれている場合、先方のプレーヤは逆順にしたり、最下位桁の文字を削ったりして後方のプレーヤの数字になるようにすることが必ずできる。
以下ソース。
string itos(int a){ stringstream ss; ss << a; return ss.str(); } class TheNumberGame { public: string determineOutcome(int A, int B) { string result; string a = itos(A); string b = itos(B); bool good = false; if(a.find(b, 0) != string::npos) good |= true; reverse(ALL(b)); if(a.find(b, 0) != string::npos) good |= true; return good ? "Manao wins" : "Manao loses"; } };
Get up! 明日のSUPER ST@R!