#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int dp[20][11][11][2];
int f(int pos, int last1, int last2, bool ok){
if(pos == s.size())
return 1;
if(dp[pos][last1][last2][ok] != -1)
return dp[pos][last1][last2][ok];
int limit = (ok == true ? s[pos] - '0' : 9);
int ans = 0;
for(int i = 0; i <= limit; i++){
if(last1 == 10 && last2 == 10 && i == 0){
if(ok == true && limit == i)
ans += f(pos + 1, last1, last2, 1);
else
ans += f(pos + 1, last1, last2, 0);
}
else {
if(i == last1 || i == last2)
continue;
if(ok == true && limit == i)
ans += f(pos + 1, i, last1, 1);
else
ans += f(pos + 1, i, last1, 0);
}
}
return ans;
}
int solve(int x){
if(x == -1)return 0;
s = to_string(x);
memset(dp, -1, sizeof(dp));
return f(0, 10, 10, 1);
}
signed main(){
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
cin.tie(nullptr)->sync_with_stdio(false);
int a, b;
cin >> a >> b;
cout << solve(b) - solve(a - 1) << endl;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |