#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
string s;
int f[20][2][11][11][2];
int dp(int i,int idx,int j,int k,int keep){
if (i>=s.size()){
return keep;
}
if (f[i][idx][j][k][keep]!=-1){
return f[i][idx][j][k][keep];
}
f[i][idx][j][k][keep]=0;
int max1;
if (idx){
max1=s[i]-'0';
}else{
max1=9;
}
int ans=0;
for (int t=0;t<=max1;t++){
if (t==0){
if (k==10){
ans+= dp(i+1,0,10,10,0);
}else{
int pre=0;
if ((t==k)||(t==j)){
pre=1;
}
ans+= dp(i+1,(t==max1)&&(idx),k,t,max(keep,pre));
}
}else{
int pre=0;
if ((t==k)||(t==j)){
pre=1;
}
ans+= dp(i+1,(t==max1)&&(idx),k,t,max(keep,pre));
}
}
return f[i][idx][j][k][keep]=ans;
}
int get(int n){
if (n==-1){
return 0;
}
s=to_string(n);
s='#'+s;
memset(f,-1,sizeof f);
return dp(1,1,10,10,0);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
a--;
cout << (b-a)-(get(b)-get(a)) << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |