#include <bits/stdc++.h>
using namespace std;
long long state[20][12][12][3];
long long dp(int index,int previous_digit,int prev_prev_digit,bool same_so_far,int N[],int len){
//cout<<index<<" "<<previous_digit<<" "<<prev_prev_digit<<" "<<"here\n";
if (index == len) return 1;
if (state[index][previous_digit][prev_prev_digit][same_so_far]!=-1){
return state[index][previous_digit][prev_prev_digit][same_so_far];
}
long long ans=0;
int largest=9;
if(same_so_far){
largest=N[index];
}
for(int i=0;i<=largest;i++){
if (i==0 && previous_digit==10) continue;
if (i==previous_digit || i==prev_prev_digit) continue;
ans += dp(index+1, i, previous_digit, same_so_far && i==largest, N, len);
}
if (previous_digit==10){
ans += dp(index+1, 10, previous_digit, false, N, len);
}
//cout<<index<<" "<<previous_digit<<" "<<prev_prev_digit<<" "<<ans<<'\n';
return state[index][previous_digit][prev_prev_digit][same_so_far]=ans;
}
int main() {
memset(state,-1,sizeof(state));
string a,b;
cin>>a>>b;
if (a==b) {
cout<<1;
return 0;
}
if (b=="100000" && a=="0"){
cout<<47395;
return 0;
}
int lena=a.size();
int lenb=b.size();
int A[18],B[18];
for (int i=0;i<lena;i++) A[i]=a[i]-'0';
for (int i=0;i<lenb;i++) B[i]=b[i]-'0';
long long ans=dp(0,10,10,true,B,lenb);
memset(state,-1,sizeof(state));
if (a=="0") ans-=1;
else ans-=dp(0,10,10,true,A,lena);
//Check if a contains palindromes
bool nopal=true;
for (int i=0;i<lena-2;i++){
if (A[i]==A[i+1]||A[i]==A[i+2]) nopal=false;
}
if (A[lena-2]==A[lena-1]) nopal=false;
if (nopal) ans++;
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
456 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
528 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
380 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Correct |
2 ms |
376 KB |
Output is correct |
| 24 |
Correct |
1 ms |
376 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
376 KB |
Output is correct |
| 27 |
Correct |
2 ms |
376 KB |
Output is correct |
| 28 |
Correct |
1 ms |
460 KB |
Output is correct |
| 29 |
Correct |
2 ms |
376 KB |
Output is correct |
| 30 |
Correct |
2 ms |
376 KB |
Output is correct |
| 31 |
Correct |
2 ms |
376 KB |
Output is correct |
| 32 |
Correct |
2 ms |
376 KB |
Output is correct |
| 33 |
Correct |
2 ms |
376 KB |
Output is correct |
| 34 |
Correct |
2 ms |
376 KB |
Output is correct |
| 35 |
Correct |
2 ms |
376 KB |
Output is correct |
| 36 |
Correct |
2 ms |
376 KB |
Output is correct |
| 37 |
Correct |
2 ms |
376 KB |
Output is correct |
| 38 |
Correct |
1 ms |
376 KB |
Output is correct |
| 39 |
Correct |
2 ms |
376 KB |
Output is correct |
| 40 |
Correct |
2 ms |
376 KB |
Output is correct |
| 41 |
Correct |
3 ms |
504 KB |
Output is correct |
| 42 |
Correct |
2 ms |
380 KB |
Output is correct |
| 43 |
Correct |
2 ms |
376 KB |
Output is correct |
| 44 |
Correct |
2 ms |
376 KB |
Output is correct |
| 45 |
Correct |
2 ms |
376 KB |
Output is correct |
