[AtCoder] ABC 146 C – Buy an Integer
問題
方針
\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません