Submission #1389731

---

Source Code Expand

#include <bits/stdc++.h>  

using namespace std;

#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define FORr(i, j, k) for(int i = j; i >= k; --i)
#define repr(i, j) FOR(i, j, 0)
#define INF (1 << 30)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

ll adp[20][2][2][2], bdp[20][2][2][2];

int main() {
	string A, B;
	cin >> A >> B;
	adp[0][0][0][0] = bdp[0][0][0][0] = 1;
	rep(i, B.size()) rep(j, 2) rep(k, 2) rep(l, 2) {
		int lim = j ? 9 : B[i] - '0';
		rep(d, lim + 1) {
			bdp[i + 1][j || d < lim][k || d == 4][l || d == 9] += bdp[i][j][k][l];
		}
	}
	rep(i, A.size()) rep(j, 2) rep(k, 2) rep(l, 2) {
		int lim = j ? 9 : A[i] - '0';
		rep(d, lim + 1) {
			adp[i + 1][j || d < lim][k || d == 4][l || d == 9] += adp[i][j][k][l];
		}
	}
	ll res = 0;
	rep (j, 2) rep (k, 2) rep (l, 2) {
    	if(k || l) res += bdp[B.size()][j][k][l];
    }
    ll tmp = 0;
    rep (j, 2) rep (k, 2) rep (l, 2) {
    	if(k || l) tmp += adp[A.size()][j][k][l];
    }
    if(A.find("4") != string::npos || A.find("9") != string::npos) ++res;
    printf("%lld\n", res - tmp);
	return 0;
}

Submission Info

Judge Result