読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

SRM 699 div2 medium LastDigit

SRM 二分探索

問題

問題概要

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;
    }
};