Submission #3789797

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;

long long int digit(long long int A){
    long long int dp[20][2][2] = {};
    
    string s = to_string(A);
    
    int n = s.size();
    
    dp[0][0][0] = 1;
    
    rep(i, n) rep(j, 2) rep(k, 2){
        int lim = j ? 9 : s[i] - '0';
        rep(d, lim+1){
            dp[i+1][j || d < lim][k || d == 4 || d == 9] += dp[i][j][k];
        }
    }
    
    return dp[n][0][1] + dp[n][1][1];
}

int main(){
    long long int A, B;
    cin >> A >> B;
    
    long long int ans = digit(B) - digit(A-1);
    
    cout << ans << endl;
}

Submission Info

Judge Result