#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#define fo(iter, start_value, less_than) for(int iter = start_value; iter<less_than; iter++)
#define noans cout<<"-1"
#define zero cout<<"0"
#define nline "\n"
#define space " "
#define MSBll(n) __lg(n)
#define vi vector<int>
#define vpii vector<pair<int, int> >
#define vvi vector<vector<int> >
#define set_bits __builtin_popcountll
#define getunique(x) {sort(all(x)); x.erase(unique(all(x)), x.end());}
#define mem(x, val) memset(x, val, sizeof(x))
// const double PI = 3.1415926535897932384626433832795;
// const string pi = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
const int mod = 1e9+7;
// const int mod = 998244353;
const ll INF = 1e18;
// const int N = 1e5+5;
// const int N = 2e5+5;
// const int N = 3e5+5;
// const int MX = INT_MAX;
// const int MN = INT_MIN;
#define int ll
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int getRandomNumber(int l, int r){
uniform_int_distribution<int> dist(l, r);
return dist(rnd);
}
#define yes cout<<"YES"
#define no cout<<"NO"
//set MULTISET ka bhi dekh lena bhai
int dp[20][2][12][12];
int rec(int i, bool tight, int prv1, int prv2, bool s, const string &str, int n){
if(i == n) return s;
int &ans = dp[i][tight][prv1+2][prv2+2];
if(ans != -1) return ans;
ans = 0;
int ub = (tight?(str[i] - '0'):9);
for(int dig = 0; dig <= ub; dig++){
if(dig == 0){
if(!s){
ans += rec(i+1, (tight&(dig == ub)), prv1, prv2, 0, str, n);
}else{
if(dig != prv1 and dig != prv2){
ans += rec(i+1, (tight&(dig == ub)), dig, prv1, (s or dig), str, n);
}
}
}else{
if(dig != prv1 and dig != prv2){
ans += rec(i+1, (tight&(dig == ub)), dig, prv1, (s or dig), str, n);
}
}
}
return ans;
}
signed main() {
// #ifndef ONLINE_JUDGE
// freopen("Error.txt", "w", stderr);
// #endif
fastio();
int l, r; cin>>l>>r;
string rstr = to_string(r);
int lans = 0, rans = 0;
memset(dp, -1, sizeof dp);
// rstr = "0000012";
rans = rec(0, 1, -1, -2, 0, rstr, rstr.size());
rans++;
if(l){
l--;
memset(dp, -1, sizeof dp);
string lstr = to_string(l);
lans = rec(0, 1, -1, -2, 0, lstr, lstr.size());
lans++;
}
cout<<(rans - lans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
352 KB |
Output is correct |
| 10 |
Correct |
1 ms |
308 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
2 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
1 ms |
340 KB |
Output is correct |
| 32 |
Correct |
1 ms |
336 KB |
Output is correct |
| 33 |
Correct |
1 ms |
340 KB |
Output is correct |
| 34 |
Correct |
1 ms |
340 KB |
Output is correct |
| 35 |
Correct |
1 ms |
332 KB |
Output is correct |
| 36 |
Correct |
1 ms |
340 KB |
Output is correct |
| 37 |
Correct |
1 ms |
332 KB |
Output is correct |
| 38 |
Correct |
1 ms |
340 KB |
Output is correct |
| 39 |
Correct |
1 ms |
340 KB |
Output is correct |
| 40 |
Correct |
1 ms |
340 KB |
Output is correct |
| 41 |
Correct |
1 ms |
340 KB |
Output is correct |
| 42 |
Correct |
1 ms |
328 KB |
Output is correct |
| 43 |
Correct |
1 ms |
340 KB |
Output is correct |
| 44 |
Correct |
1 ms |
340 KB |
Output is correct |
| 45 |
Correct |
1 ms |
332 KB |
Output is correct |
