Submission #1500660

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

typedef long long ll;
ll A, B;
//string A, B;
ll data[20];
ll dp[20][2][2];/*
ll dpA[20][2][2];
ll dpB[20][2][2];*/

ll Func(ll n){
    string str = to_string(n);

    for(int i = 0; i < 20; ++i){
        for(int j = 0; j < 2; ++j){
            for(int k = 0; k < 2; ++k){
                dp[i][j][k] = 0;
            }
        }
    }

    dp[0][0][0] = 1;
    for(int i = 0; i < str.length(); ++i){
        for(int j = 0; j < 2; ++j){
            for(int k = 0; k < 2; ++k){
                int l = j ? 9 : int(str[i] -  '0');
                for(int d = 0; d <= l; ++d){
                    dp[i + 1][j || d < l][k || d == 4 || d == 9] += dp[i][j][k];
                }
            }
        }
    }

    ll ans = 0;
    for(int j = 0; j < 2; ++j){
        ans += dp[str.length()][j][1];
    }
    return ans;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> A >> B;

    cout << Func(B) - Func(A - 1) << endl;
    
    return 0;
}

Submission Info

Judge Result