Submission #1986051

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <complex>
#include <set>
#include <list>
#include <iomanip>
#include <map>
#include <memory.h>
#include <functional>


using namespace std;
static const double EPS = 1e-9;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a,0,sizeof(a))
#define minus(a) memset(a,0xff,sizeof(a))
#define chmax(a,b) a=min((a),(b))
#define chmin(a,b) a=max((a),(b))


#define MOD 1000000007

typedef pair<int,int>P;
#define INF (1<<29)
 
struct edge { 
	int from, to; 
	edge (int from, int to){
		this->from=from; this->to=to;
	}
};
 
int V,E;
typedef vector<edge> edges;
vector<edges> G;

ll dp[20][2][2];

ll go(string n) {
	memset(dp, 0, sizeof(dp));
	int D;
	dp[0][0][0] = 1;
	rep(i, n.size()) {
		D = n[i] - '0';
		rep(j, 2) {
			rep(k, 2) {
				for (int d = 0; d <= ((j == 1) ? 9 : D); d++) {
					dp[i + 1][j | (d < D)][k | (d == 4) | (d == 9)] += dp[i][j][k];
				}
			}

		}
	}
	return dp[n.size()][0][1] + dp[n.size()][1][1];
}

int main(){

	ll a, b;
	cin >> a >> b;

	cout << go(to_string(b)) - go(to_string(a-1)) << endl;

	return 0;
}

Submission Info

Judge Result