Submission #1985413

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll a,b;
ll dp[20][2][2];

template <typename T> string to_string(const T& n) {
  ostringstream st;
  st << n;
  return st.str();
}

ll solve(string s) {
  memset(dp,0,sizeof dp);
  dp[0][0][0] = 1;

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

int main() {
  cin >> a >> b;
  ostringstream sa,sb;
  sa << a-1;
  sb << b;

  cout << solve(sb.str()) - solve(sa.str()) << endl;
}

Submission Info

Judge Result