Skip to content

Instantly share code, notes, and snippets.

@takageymt
Created March 9, 2017 03:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save takageymt/635688e448c29da9a3211217ed34c93a to your computer and use it in GitHub Desktop.
Save takageymt/635688e448c29da9a3211217ed34c93a to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})
const int inf = 1LL << 55;
const int mod = 1e9 + 7;
int solve(string s) {
int len = s.size();
int dp[20][2][2][2] = {};
dp[0][0][0][0] = 1;
rep(i, len) rep(j, 2) rep(k, 2) rep(l, 2) {
int lim = j ? 9 : s[i]-'0';
rep(d, lim+1) {
dp[i+1][j||d <lim][k||d==4][l||d==9] += dp[i][j][k][l];
}
}
int res = 0;
rep(j, 2) rep(k, 2) rep(l, 2) {
if(k || l) res += dp[len][j][k][l];
}
return res;
}
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
cout << fixed << setprecision(12);
int A, B;
cin >> A >> B;
string a = to_string(A-1);
string b = to_string(B);
cout << solve(b) - solve(a) << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment