Submission #162815

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

ll dp[40][2];

ll rec(int i, int f, const std::string &s){
    if(i == (int)s.size()){return 1ll;}
    if(dp[i][f] != -1){return dp[i][f];}

    int max = f?9:s[i]-'0';
    ll res = 0;
    for(int nn=0;nn<=max;nn++){
        if(nn == 4 || nn == 9){continue;}
        res += rec(i+1, f || (nn != max), s);
    }

    return dp[i][f] = res;
}

ll count(const std::string &s){
    REP(i, 40){REP(j, 2){dp[i][j] = -1;}}

    return rec(0, 0, s);
}

int main(){
    ll a, b;
    std::cin >> a >> b;

    std::string A = std::to_string(a-1), B = std::to_string(b);

    printf("%lld\n", (b+1-a) - (count(B)-count(A)));
}

Submission Info

Judge Result