p258.ans1
======================
81

=================
p258.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int A, B;

map<string, int64_t> answer_for_9s = {
    {"99", 81},
    {"9999", 7389},
    {"999999", 676133},
    {"99999999", 62563644},
    {"9999999999", 1550148951}
};

void read() { cin >> A >> B; }

int solve_dp(string bound) {
    int n = bound.size() / 2;
    assert(n * 2 == bound.size());

    // dp[pos][balance + 100][max_increase][max_decrease][tight][changed]
    // balance: difference between first half sum and second half sum (offset by
    // 100) max_increase/decrease: max possible change from modifying one digit
    // tight: whether we're still bounded by the input
    // changed: whether we've already changed a digit
    vector<vector<vector<vector<vector<vector<int>>>>>> dp(
        11, vector<vector<vector<vector<vector<int>>>>>(
                201, vector<vector<vector<vector<int>>>>(
                         10, vector<vector<vector<int>>>(
                                 10, vector<vector<int>>(2, vector<int>(2, -1))
                             )
                     )
            )
    );

    function<int(int, int, int, int, bool, bool)> rec =
        [&](int pos, int balance, int max_inc, int max_dec, bool tight,
            bool changed) -> int {
        if(pos == bound.size()) {
            // Check if this can be made almost lucky
            bool can_be_almost_lucky = false;

            // Only non-lucky numbers can be almost lucky
            if(balance != 0) {
                // Can become lucky by increasing a digit to reduce negative
                // balance
                if(balance < 0 && max_inc >= -balance) {
                    can_be_almost_lucky = true;
                }
                // Can become lucky by decreasing a digit to reduce positive
                // balance
                if(balance > 0 && max_dec >= balance) {
                    can_be_almost_lucky = true;
                }
            }

            return can_be_almost_lucky ? 1 : 0;
        }

        if(dp[pos][balance + 100][max_inc][max_dec][tight][changed] != -1) {
            return dp[pos][balance + 100][max_inc][max_dec][tight][changed];
        }

        int limit = tight ? (bound[pos] - '0') : 9;
        int result = 0;

        for(int digit = (pos == 0 ? 1 : 0); digit <= limit; digit++) {
            int new_balance = balance;
            int new_max_inc = max_inc;
            int new_max_dec = max_dec;

            if(pos < n) {
                // First half - digit contributes positively to balance
                new_balance += digit;
                // Can decrease this digit by at most 'digit' (but not to 0 if
                // pos==0) Can increase by at most (9-digit)
                if(pos == 0) {
                    new_max_dec =
                        max(new_max_dec,
                            digit - 1);  // Can't make first digit 0
                } else {
                    new_max_dec = max(new_max_dec, digit);
                }
                new_max_inc = max(new_max_inc, 9 - digit);
            } else {
                // Second half - digit contributes negatively to balance
                new_balance -= digit;
                // Can increase this digit by at most (9-digit), or decrease by
                // at most 'digit'
                new_max_inc = max(new_max_inc, digit);
                new_max_dec = max(new_max_dec, 9 - digit);
            }

            bool new_tight = tight && (digit == limit);

            result +=
                rec(pos + 1, new_balance, new_max_inc, new_max_dec, new_tight,
                    changed);
        }

        return dp[pos][balance + 100][max_inc][max_dec][tight][changed] =
                   result;
    };

    return rec(0, 0, 0, 0, true, false);
}

int solve(int n) {
    if(n <= 0) {
        return 0;
    }

    int c_digits_n = 0;
    int tmp = n;
    while(tmp) {
        c_digits_n++;
        tmp /= 10;
    }

    int64_t ans = 0;
    string bound;
    for(int cnt_digits = 2; cnt_digits <= c_digits_n; cnt_digits += 2) {
        if(cnt_digits == c_digits_n) {
            bound = to_string(n);
            ans += solve_dp(bound);
        } else {
            bound = string(cnt_digits, '9');
            if(answer_for_9s.count(bound)) {
                ans += answer_for_9s[bound];
            } else {
                ans += solve_dp(bound);
            }
        }
    }

    return ans;
}

void solve() {
    int result_B = solve(B);
    int result_A = (A > 0) ? solve(A - 1) : 0;
    cout << result_B - result_A << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p258.in1
======================
1 99


=================
statement.txt
======================
258. Almost Lucky Numbers
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The number is called lucky if it consists of 2N digits and the sum of the first N digits is equal to the sum of the last N digits. The number is called almost lucky, if it is possible to change one of its digits to some other in such a way, that a new number is lucky. Your task is to find the count of almost lucky numbers in the interval from A to B (including A and B).

The first digit can't be changed to zero because of leading zeroes are not allowed.

Input
The only line of the input file contains two integer numbers A and B (0 <= A <= B <= 10^9).

Output
Output the only number - the requested number of almost lucky numbers.

Sample test(s)

Input
1 99

Output
81

Note
All two-digits not lucky numbers are almost lucky.
Author:	Andrew V. Lazarev
Resource:	Saratov SU Contest: Golden Fall 2004
Date:	October 2, 2004






=================
