[AtCoder] ABC 146 C – Buy an Integer

2019年11月25日

問題

方針

\( f(N) = AN + Bd(N)\) とすると、\( f(N) \) は増加関数なので、二分探索を行います。整数の桁数は、対数を使うよりも、数値を文字列に変換してから長さを得る方が良いと思います。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll A, B, X;
    cin >> A >> B >> X;
    if (A + B > X) {
        cout << "0\n";
        return 0;
    }
    ll l = 0;
    ll r = pow(10, 9) + 1;
    ll ans = 0;
    while (r - l > 1) {
        ll m = (r + l) / 2;
        ll v = A * m + to_string(m).size() * B;
        if (v <= X) {
            ans = max(ans, m);
            l = m;
        } else {
            r = m;
        }
    }
    cout << ans << "\n";
    return 0;
}