SRM 574 Div1 275 TheNumberGame

2013-03-26

00:54 |

a, b が整数 A, B を持っている。１ターンで自分の数字の順番を逆にするか下１桁を消すことができる。1000回以内にA=Bになれば a の勝ち、そうでなければ負け。
２人が最適に行動したとき a が勝つかどうかを求める。
1≦A, B≦999,999,999, A!=B, A,B には10進表記で 0 は含まれない

数字はせいぜい 9 桁なので、1000回もあれば勝敗はついていると思われる。→この条件は忘れる
b は数字を消すと負ける可能性が高まるはず. せっかく 789 だったのに 78 にするなんて！
なので、b はひたすら B をひっくり返していればいい
A から作れる数字をすべてリストアップして、それに B が含まれれば a が勝つ。

Accepted

つまり A に B か B の逆が含まれればよいのか... と思ってみるとこの実装はやぼったい。

class TheNumberGame {
	public:
	string determineOutcome(int A, int B) {
		vector<string> w;     // なにこれ
		stringstream ss, sb;
		sb<<B;
		ss<<A;
		string s=ss.str();
		REP(i, 2) {
			if(i==1) reverse(ALL(s));
			REP(sj, s.size()) {
				RANGE(ej, sj, s.size()) {
//					cout<<s.substr(sj, ej-sj+1)<<endl;
					if(s.substr(sj, ej-sj+1)==sb.str()) return "Manao wins";
				}
			}
		}
		return "Manao loses";
	}
};