Submission #1698536

---

Source Code Expand

////////////////////////////////////////////////////////////////////
// This source code is for Visual Studio
////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <stack>
#include <functional>
#include <iomanip>
#include <string>
#include <cstring>
#include <deque>
#include <math.h>

#define	numberof(a)	(sizeof(a) / sizeof(a[0]))
#define	INF		UINT64_MAX
#define Rep(i,n) for(int i = 0; i < (n); ++i )

using namespace std;

typedef vector< vector<int> > MAT;
typedef pair<int, int> PINT;
typedef long long ll;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int32_t s32;
typedef int64_t s64;

ll solve( ll inp )
{
	vector< vector<ll> > dp(20, vector<ll>(2, 0));	// dp[i][j] j = 1: 未満
	string input_str = to_string(inp);
	ll len = input_str.length();

	dp[0][0] = 1;

	for (int i = 1; i <= len; ++i ) {
		int val = input_str[i - 1] - '0';

		Rep(j, 2) {
			for (int digit = 0; digit <= ((j == 1) ? 9 : val); digit++ ) {
				if (digit == 4 || digit == 9) continue;

				dp[i][j || digit < val] += dp[i - 1][j];	// 各digitごとに前の桁のを足し上げる
			}
		}
	}

	return dp[len][0] + dp[len][1];
}

int main()
{
	ll ret = 0;
	ll A = 0;
	ll B = 0;

	cin >> A >> B;

	ret = (B - A + 1) - (solve(B) - solve(A - 1));
	cout << ret << endl;

	return 0;
}

Submission Info

Judge Result