Submission #1240777

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




typedef long long ll;
ll A, B;
ll dp[20][2][2];
ll count(ll x) {
    string s = to_string(x);
    int n = s.length();

    rep(i, 0, 20) rep(ng, 0, 2) rep(f, 0, 2) dp[i][ng][f] = 0;
    dp[0][0][1] = 1;

    rep(i, 0, n) rep(ng, 0, 2) rep(f, 0, 2) {
        int ma = 10;
        if (f == 1) ma = s[i] - '0' + 1;
        rep(j, 0, ma) {
            if(f == 1 && j == ma-1) dp[i + 1][ng | (j == 4) | (j == 9)][1] += dp[i][ng][f];
            else dp[i + 1][ng | (j == 4) | (j == 9)][0] += dp[i][ng][f];
        }
    }

    return dp[n][1][0] + dp[n][1][1];
}
//-----------------------------------------------------------------------------------
int main() {
    cin >> A >> B;
    cout << count(B) - count(A - 1) << endl;
}

Submission Info

Judge Result