The Polar Express

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4ll L, R; int sum, ans; ll dp[20][2][163];
    5ll fun(string s, int idx, bool lmt, int ds) {
    6    if (idx == s.size()) return ds == sum;
    7    if (dp[idx][lmt][ds] != -1) return dp[idx][lmt][ds];
    8    int up = lmt ? s[idx] - '0' : 9; ll cnt = 0;
    9    for (int i = 0; i <= up; i++) 
    10        cnt += fun(s, idx + 1, lmt & (i + '0' == s[idx]), ds + i);
    11    return dp[idx][lmt][ds] = cnt;
    12}
    13ll solve(ll val) {
    14    string s = to_string(val); memset(dp, -1, sizeof(dp));
    15    return fun(s, 0, 1, 0);
    16}
    17int main() {
    18    ios::sync_with_stdio(0); cin.tie(0);
    19    cin >> L >> R;
    20    for (sum = 1; sum <= 9 * 18; sum++) {
    21        if (solve(R) - solve(L-1) > 0) ans++;
    22    }
    23    cout << ans << "\n";
    24}