#include<bits/stdc++.h>
using namespace std;
long long c,d,e,zx,xc,i,j,ii,jj,dp[22][12][12],p[22],pi,pas;
string a,b,aa,bb;
void rec(long long q, bool bo1, bool bo2){
//cout<<q<<" x "<<bo1<<" "<<bo2<<" "<<pi<<endl;
//for(long long h=1; h<=pi; h++) cout<<p[h]<<" kala ";
//cout<<endl;
if(q>=a.size()){
//cout<<"CAT"<<endl<<endl<<endl;
pas++;
return;
}
if(bo1==1&&bo2==1){
//cout<<"DOG"<<endl<<endl<<endl;
if(a.size()-q>=2){
for(i=0; i<=9; i++){
for(j=0; j<=9; j++){
if(i==j) continue;
if(p[pi]==i||p[pi]==j||p[pi-1]==i) continue;
pas+=dp[a.size()-q][i][j];
}
}
}else{
for(i=0; i<=9; i++){
if(i!=p[pi]&&i!=p[pi-1]) pas+=dp[1][i][0];
}
}
return;
}
for(long long h=0; h<=9; h++){
if(bo1==0&&h<a[q]-'0') continue;
if(bo2==0&&h>b[q]-'0') continue;
if(pi>0&&h==p[pi]) continue;
if(pi>1&&h==p[pi-1]) continue;
bool qw=bo1,we=bo2;
if(h>a[q]-'0') qw=1;
if(h<b[q]-'0') we=1;
pi++;p[pi]=h;
rec(q+1,qw,we);
pi--;
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
while(a.size()<b.size()) a.insert(0,"0");
dp[0][0][0]=1;
for(i=0; i<=9; i++) dp[1][i][0]=1;
for(i=2; i<=19; i++){
for(ii=0; ii<=9; ii++){
for(j=0; j<=9; j++){
if(ii==j) continue;
if(i==2){
dp[i][ii][j]+=dp[i-1][j][0];
continue;
}
for(jj=0; jj<=9; jj++){
if(ii==jj||j==jj) continue;
dp[i][ii][j]+=dp[i-1][j][jj];
}
}
}
}
p[0]=-1;
rec(0,0,0);
cout<<pas;
return 0;
}
Compilation message
numbers.cpp: In function 'void rec(long long int, bool, bool)':
numbers.cpp:9:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q>=a.size()){
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 8 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 15 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
4 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 8 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 9 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 10 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 13 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 14 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 15 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
4 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
4 ms |
384 KB |
Output is correct |
| 21 |
Correct |
5 ms |
384 KB |
Output is correct |
| 22 |
Correct |
5 ms |
384 KB |
Output is correct |
| 23 |
Correct |
5 ms |
384 KB |
Output is correct |
| 24 |
Correct |
5 ms |
420 KB |
Output is correct |
| 25 |
Correct |
5 ms |
384 KB |
Output is correct |
| 26 |
Correct |
5 ms |
384 KB |
Output is correct |
| 27 |
Correct |
5 ms |
384 KB |
Output is correct |
| 28 |
Correct |
5 ms |
384 KB |
Output is correct |
| 29 |
Correct |
5 ms |
384 KB |
Output is correct |
| 30 |
Correct |
5 ms |
384 KB |
Output is correct |
| 31 |
Correct |
4 ms |
384 KB |
Output is correct |
| 32 |
Correct |
4 ms |
384 KB |
Output is correct |
| 33 |
Correct |
5 ms |
384 KB |
Output is correct |
| 34 |
Correct |
5 ms |
384 KB |
Output is correct |
| 35 |
Correct |
4 ms |
384 KB |
Output is correct |
| 36 |
Correct |
4 ms |
384 KB |
Output is correct |
| 37 |
Correct |
5 ms |
384 KB |
Output is correct |
| 38 |
Correct |
4 ms |
384 KB |
Output is correct |
| 39 |
Correct |
5 ms |
384 KB |
Output is correct |
| 40 |
Correct |
4 ms |
384 KB |
Output is correct |
| 41 |
Correct |
5 ms |
384 KB |
Output is correct |
| 42 |
Correct |
5 ms |
384 KB |
Output is correct |
| 43 |
Correct |
5 ms |
384 KB |
Output is correct |
| 44 |
Correct |
5 ms |
384 KB |
Output is correct |
| 45 |
Correct |
5 ms |
384 KB |
Output is correct |
