Submission #3789779

---

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 = (int)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];
        }
    }
    
    int sum = 0;
    rep(j, 2){
        sum += dp[n][j][1];
    }
    
    return sum;
}

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