二分探索するだけやんけ・・・・

と思ったけどコーナケースとか諸々で死んだよ！

#include <bits/stdc++.h>

#define INF 1e9
using namespace std;

#define REPR(i, n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

typedef long long ll;

int main() {
    ll A, B, X;
    cin >> A >> B >> X;

    const ll start = 1e9;
    ll nowp = start / 2;
    ll now = nowp/2;
    while (now > 0) {
        // cout << "Now: " << nowp << "change: " << now;
        ll cost = (nowp * A) + (B * to_string(nowp).size());
        // 購入可能
        if (X > cost) {
            // cout << "can buy" << endl;
            // 1e9が買えるなら終了
            if (nowp>=INF && nowp > 0) {
                cout << ll(1e9) << endl;
                return 0;
            }
            ll c_cost = ((nowp+1) * A) + (B * to_string(nowp+1).size());
            // +1して超えてしまうようならそれが答え
            if (X < c_cost && nowp > 0) {
                cout << nowp << endl;
                return 0;
            }
            nowp += now;
        }
        // 解ぴったりになる場合それも答え
        else if (X==cost) {
            cout << nowp << endl;
            return 0;
        }
        // 所持金が下回る場合(購入不可の場合)
        else {
            // cout << "cant buy" << endl;
            nowp -= now;
        }
        if (now%2==1 && now!=1) now+=1;
        now/=2;
    }
    if (nowp <= 0) {
        cout << 0 << endl;
        return 0;
    }
    cout << nowp << endl;

}

okimoti code

これはコンテスト中に書いたコード

計算で出した、ansN が max_Nよりも大きい桁数だとバグることに気づくまで死ぬほど時間かかった(二日)

#include <bits/stdc++.h>

#define INF 1e9
using namespace std;

#define REPR(i, n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

typedef unsigned long long ll;

unsigned  GetDigit(ll num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

int main() {
    ll A, B, X;
    cin >> A >> B >> X;
    // Nのdigitを求める
    ll digits = 1;
    ll N = 1;
    ll c=(A * N) + (B * digits);
    bool updated = false;
    while (X >= c) {
        updated = true;
        N *= 10;
        digits++;
        c=(A * N) + (B * digits);
    }

    if (!updated) {
        cout << 0 << endl;
        return 0;
    }
    // Nが1でも買えない場合
    ll max_N = N - 1;
    digits--;
    //残り金額
    ll last = X - (B * digits);
    ll ansN = last/A;
    if (1000000000
        <= (ansN))
        cout << 1000000000
             << endl;
    else cout << ansN << endl;
    ll d = GetDigit(ansN);
    ll n = GetDigit(max_N);

    if (d != n) throw  "Err";

    return 0;
}