Submission #163386

---

Source Code Expand

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <sstream>

using namespace std;


typedef long long int ll;
ll A, B;

map<ll, ll> dp;

ll f(ll n) {
	stringstream ss;
	if (dp.find(n) != dp.end())
		return dp[n];

	if (n < 3) {
		return 0;
	} else if (n <= 4) {
		return 1;
	} else if (n <= 9) {
		return 2;
	}


	ll ret = 0;
	for (int i = 0; i <= 9; i++) {
		if (i <= n%10) {
			if (i == 4 || i == 9) {
				ret += (n / 10) + 1;
			} else {
				ret += f(n/10);
			}
		} else {
			if (i == 4 || i == 9) {
				ret += (n / 10);
			} else {
				ret += f((n/10)-1);
			}
		}
	}
	dp[n] = ret;
	return ret;

}

int main(int argc, const char * argv[])
{
	cin >> A >> B;

	ll x = f(B) - f(A-1);
	cout << x << endl;


}

Submission Info

Judge Result