Submission #1352135

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
template<class T>bool chmin(T&a,const T&b){return a>b?(a=b,true):false;}
template<class T>bool chmax(T&a,const T&b){return a<b?(a=b,true):false;}

ll dp[20][2]; // [k 桁目まで見た][isSmaller]
ll f(ll A) {
  memset(dp, 0, sizeof(dp));
  vector<int> d;
  for (ll t = A; t > 0; ) {
    d.push_back(t % 10);
    t /= 10;
  }
  reverse(d.begin(), d.end());
  int N = d.size();
  dp[0][0] = 1;
  for (int i = 0; i < N; i++) {
    for (int s = 0; s < 2; s++) {
      for (int digit = 0; digit <= 9; digit++) {
        if (digit == 4 || digit == 9) continue;
        if (s == 1) {
          dp[i+1][s] += dp[i][s];
        } else if (s == 0 && d[i] > digit) {
          dp[i+1][1] += dp[i][s];
        } else if (s == 0 && d[i] == digit) {
          dp[i+1][s] += dp[i][s];
        }
      }
    }
  }
  ll ans = dp[N][0] + dp[N][1];
  return ans;
}

int main2() {
  ll A, B;
  cin >> A >> B;
  ll ok = f(B) - f(A-1);
  ll all = B - A + 1;
  cout << all - ok << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}

Submission Info

Judge Result