Submission #1498314

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
const int INF = 1e9;

int dp[30][2][2];

int countKinsi(int A_)
{
    string A = to_string(A_);

    REP(i,30) REP(j,2) REP(k,2) dp[i][j][k] = 0;

    int n = A.length();
    dp[0][0][0] = 1;
    //j:A未満であることが確定している
    //k:禁止された数字である
    REP(i,n) REP(j,2) REP(k,2) {
        int lim = j ? 9 : A[i] - '0';
        REP(d, lim + 1) {
            dp[i + 1][j || d < lim][k || d == 4 || d == 9] += dp[i][j][k];
        }
    }

    int ret = 0;
    REP(j,2) ret += dp[n][j][1];
    return ret;
}

signed main()
{
    int A, B;

    cin >> A >> B;
    cout << countKinsi(B) - countKinsi(A - 1) << endl;
}

Submission Info

Judge Result