#include <bits/stdc++.h>
using namespace std;
long long dp[23][13][13][2];
int cifre[23];
long long digit_dp(long long val){
if(val<10)
return val+1;
int nrc=0;
while(val){
cifre[++nrc]=val%10;
val/=10;
}
int cif1,cif2,cif3,nrcif;
for(cif1=0;cif1<10;++cif1)
for(cif2=0;cif2<10;++cif2)
if(cif1!=cif2){
dp[2][cif1][cif2][0]=1;
if(10*cif1+cif2<=10*cifre[2]+cifre[1])
dp[2][cif1][cif2][1]=1;
}
for(nrcif=3;nrcif<=nrc;++nrcif)
for(cif1=0;cif1<10;++cif1)
for(cif2=0;cif2<10;++cif2)
if(cif1!=cif2){
dp[nrcif][cif1][cif2][0]=0;
dp[nrcif][cif1][cif2][1]=0;
for(cif3=0;cif3<10;++cif3)
if(cif1!=cif3){
if(cif1>cifre[nrcif])
dp[nrcif][cif1][cif2][0]+=dp[nrcif-1][cif2][cif3][0];
else
if(cif1<cifre[nrcif]){
dp[nrcif][cif1][cif2][0]+=dp[nrcif-1][cif2][cif3][0];
dp[nrcif][cif1][cif2][1]+=dp[nrcif-1][cif2][cif3][0];
}
else{
dp[nrcif][cif1][cif2][0]+=dp[nrcif-1][cif2][cif3][0];
dp[nrcif][cif1][cif2][1]+=dp[nrcif-1][cif2][cif3][1];
}
}
}
long long ans=10;
for(nrcif=2;nrcif<=nrc;++nrcif)
for(cif1=1;cif1<10;++cif1)
for(cif2=0;cif2<10;++cif2)
ans+=dp[nrcif][cif1][cif2][nrcif==nrc];
return ans;
}
int main()
{
long long a,b;
cin>>a>>b;
cout<<digit_dp(b)-digit_dp(a-1);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |