SRM 699 div2 medium LastDigit
問題概要
564が与えられた場合は答えは、509となる。これは、564=509+50+5となるからである。このように、下1桁を消していって、その合計が、与えられた数と同じになる数字があるかを調べる。同じものがなければ、-1を返す。
解法
二分探索でやった。下一けたを削って足していくので、答えとする数字が大きければ、それだけ合計の値も大きくなる。よって、単調性があるので、二分探索で値を絞っていくことができる。
ミス
これも時間かった。
コード
class LastDigit { public: ll che(ll mid){ ll ans = mid; string d; d = to_string(mid); for (int i = 1; i < d.size(); ++i){ string t = d.substr(0, i); ans += stoll(t); } return ans; } long long findX(long long S){ ll l = 0, r = S + 1; for (int i = 0; i < 1000; ++i){ ll mid = (l + r) / 2; if(che(mid) >= S){ r = mid; }else{ l = mid; } } ll ret = -1; for (ll i = l; i <= r; ++i){ if(S == che(i)){ ret = i; } } return ret; } };