SRM574 Div2 Medium "TheNumberGameDiv2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12474
訳
Number Gameと呼ばれる一人でやるゲームがある。
まずナンバーAとBが与えられる。
AとBにはどちらも0は含んでいない。
AをBに変換したい。
1ターンでプレイヤーは現在のナンバーをひっくり返すか、10で割ることが出来る。
例えば現在のナンバーが12849だとすると、ひっくり返して94821とするか、
10で割って1284とすることが出来る。(割った時の余りはいつも切り捨てられる)
A Bが与えられる。AからBへ変換することが可能ならば、
それにかかる最小ターン数を返せ。
無理ならば-1を返せ。
制約
1 <= A, B <= 999,999,999
A != B
考えた事
A Bを文字列として考える。
まずAの中にBが含まれるか、
Bをリバースしたものが含まれていなければ変換はできない。
- Bが含まれている場合
Aのindex0からBが含まれていれば、
10で割っていっていらない部分を切るだけでよい。
答えはいらない部分の数となる。
そうでなければひっくり返して前のいらない部分を切り落とし、
もう一度ひっくり返して後ろのいらない部分を切り落とさなければならないので、
答えはいらない部分 + 2となる。
- Bをリバースしたものが含まれている場合
まず後ろのいらない部分を切り落とし、
ひっくり返して前のいらない部分を切り落とせばよいので
答えはいらない部分 + 1となる。
ソースコード
class TheNumberGameDiv2 { public: int minimumMoves(int A, int B){ // A Bを文字列へ ostringstream oss; oss << A; string a = oss.str(); oss.str(""); oss.clear(stringstream::goodbit); oss << B; string b = oss.str(); int res = INT_MAX; // 順で試す int s = a.find( b ); if( s == 0 ){ res = min( res, (int)(a.length() - b.length()) ); }else if( s != -1 ){ res = min( res, (int)(a.length() - b.length()) + 2 ); } // 逆で試す reverse( b.begin(), b.end() ); s = a.find( b ); if( s != -1 ){ res = min( res, (int)(a.length() - b.length()) + 1 ); } if( res == INT_MAX ) res = -1; return res; } };