#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,sz;
string a,b,aa,bb;
void rec(long long q, bool bo1, bool bo2, long long w){
//cout<<q<<" "<<bo1<<" "<<bo2<<" "<<w<<" x "<<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){
long long hj=pas;
if(a.size()-q>=2){
for(i=0; i<=9; i++){
for(j=0; j<=9; j++){
if(i==j) continue;
if((w<pi&&p[pi]==i)||(w<pi&&p[pi]==j)||(w<pi-1&&p[pi-1]==i)) continue;
pas+=dp[a.size()-q][i][j];
}
}
}else{
for(i=0; i<=9; i++){
if((i==p[pi]&&w<pi)||(i==p[pi-1]&&w<pi-1)) continue;
pas+=dp[1][i][0];
}
}
//cout<<"DOG +"<<pas-hj<<endl<<endl<<endl;
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>w&&h==p[pi]) continue;
if(pi-1>w&&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;
if(w==100&&h!=0) rec(q+1,qw,we,q); else rec(q+1,qw,we,w);
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,100);
cout<<pas;
return 0;
}
Compilation message
numbers.cpp: In function 'void rec(long long int, bool, bool, long long int)':
numbers.cpp:9:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q>=a.size()){
~^~~~~~~~~~
numbers.cpp:15:13: warning: unused variable 'hj' [-Wunused-variable]
long long hj=pas;
^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is 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 |
4 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
280 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
4 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
4 ms |
384 KB |
Output is correct |
| 19 |
Correct |
4 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 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 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
4 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
4 ms |
384 KB |
Output is correct |
| 16 |
Correct |
4 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
4 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
5 ms |
384 KB |
Output is correct |
| 22 |
Correct |
4 ms |
384 KB |
Output is correct |
| 23 |
Correct |
4 ms |
384 KB |
Output is correct |
| 24 |
Correct |
4 ms |
384 KB |
Output is correct |
| 25 |
Correct |
4 ms |
384 KB |
Output is correct |
| 26 |
Correct |
5 ms |
384 KB |
Output is correct |
| 27 |
Correct |
4 ms |
384 KB |
Output is correct |
| 28 |
Correct |
4 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 |
5 ms |
384 KB |
Output is correct |
| 32 |
Correct |
5 ms |
384 KB |
Output is correct |
| 33 |
Correct |
5 ms |
384 KB |
Output is correct |
| 34 |
Correct |
4 ms |
384 KB |
Output is correct |
| 35 |
Correct |
4 ms |
384 KB |
Output is correct |
| 36 |
Correct |
5 ms |
384 KB |
Output is correct |
| 37 |
Correct |
5 ms |
384 KB |
Output is correct |
| 38 |
Correct |
5 ms |
384 KB |
Output is correct |
| 39 |
Correct |
5 ms |
384 KB |
Output is correct |
| 40 |
Correct |
5 ms |
384 KB |
Output is correct |
| 41 |
Correct |
5 ms |
384 KB |
Output is correct |
| 42 |
Correct |
4 ms |
384 KB |
Output is correct |
| 43 |
Correct |
5 ms |
384 KB |
Output is correct |
| 44 |
Correct |
4 ms |
384 KB |
Output is correct |
| 45 |
Correct |
5 ms |
384 KB |
Output is correct |
