#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define pb push_back
#define mp make_pair
#define READS(x); string x;cin >> x;
#define READ(x); int x;cin >> x;
#define DOUREAD(x,y); int x,y;cin >> x >> y;
#define TRIREAD(x,y,z); int x,y,z;cin >> x >> y >> z;
int dp[25][15][15][2][2];
string S;
int LIM;
int F(int POS,int PRE,int CUR,int FLAG,int ZERO){
if(POS == LIM) return 1;
if(dp[POS][PRE][CUR][FLAG][ZERO] != -1) return dp[POS][PRE][CUR][FLAG][ZERO];
int& ANS = dp[POS][PRE][CUR][FLAG][ZERO];
ANS = 0;
int BOUND;
if(FLAG) BOUND = 9;
else BOUND = S[POS+1]-'0';
for(int d = 0 ; d <= BOUND ; d++){
if(d == CUR) continue;
if(d == PRE) continue;
int BOOL;
if(FLAG) BOOL = 1;
else{
if(d < BOUND) BOOL = 1;
else BOOL = 0;
}
int NPRE = PRE;
int NCUR = CUR;
int NZ = (ZERO|(d > 0));
if(NZ){
NPRE = CUR;
NCUR = d;
}
ANS += F(POS+1,NPRE,NCUR,BOOL,NZERO);
}
return ANS;
}
signed main(){fast
DOUREAD(L,R);
if(L <= 1){
memset(dp,-1,sizeof(dp));
S = to_string(R);
LIM = S.size();
S = '_' + S;
int ANZ = F(0,10,10,0,0);
if(L == 1) cout << ANZ - 1 << '\n';
else cout << ANZ << '\n';
}
if(L > 1){
L--;
S = to_string(L);
LIM = S.size();
S = '_' + S;
memset(dp,-1,sizeof(dp));
int ANSL = F(0,10,10,0,0);
memset(dp,-1,sizeof(dp));
S = to_string(R);
LIM = S.size();
S = '_' + S;
int ANSR = F(0,10,10,0,0);
cout << ANSR - ANSL << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 5 |
Correct |
0 ms |
604 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
464 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 9 |
Correct |
0 ms |
604 KB |
Output is correct |
| 10 |
Correct |
0 ms |
604 KB |
Output is correct |
| 11 |
Correct |
0 ms |
604 KB |
Output is correct |
| 12 |
Correct |
1 ms |
604 KB |
Output is correct |
| 13 |
Correct |
0 ms |
604 KB |
Output is correct |
| 14 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 15 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 16 |
Correct |
1 ms |
604 KB |
Output is correct |
| 17 |
Correct |
1 ms |
604 KB |
Output is correct |
| 18 |
Correct |
0 ms |
604 KB |
Output is correct |
| 19 |
Correct |
0 ms |
604 KB |
Output is correct |
| 20 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 9 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 11 |
Correct |
0 ms |
600 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 13 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 14 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 15 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 16 |
Correct |
1 ms |
600 KB |
Output is correct |
| 17 |
Correct |
1 ms |
600 KB |
Output is correct |
| 18 |
Correct |
0 ms |
604 KB |
Output is correct |
| 19 |
Correct |
1 ms |
604 KB |
Output is correct |
| 20 |
Correct |
0 ms |
604 KB |
Output is correct |
| 21 |
Correct |
0 ms |
604 KB |
Output is correct |
| 22 |
Correct |
0 ms |
604 KB |
Output is correct |
| 23 |
Correct |
1 ms |
604 KB |
Output is correct |
| 24 |
Correct |
0 ms |
604 KB |
Output is correct |
| 25 |
Correct |
0 ms |
604 KB |
Output is correct |
| 26 |
Correct |
0 ms |
604 KB |
Output is correct |
| 27 |
Correct |
0 ms |
604 KB |
Output is correct |
| 28 |
Correct |
0 ms |
604 KB |
Output is correct |
| 29 |
Correct |
0 ms |
460 KB |
Output is correct |
| 30 |
Correct |
0 ms |
464 KB |
Output is correct |
| 31 |
Correct |
0 ms |
604 KB |
Output is correct |
| 32 |
Correct |
0 ms |
604 KB |
Output is correct |
| 33 |
Correct |
0 ms |
604 KB |
Output is correct |
| 34 |
Correct |
0 ms |
604 KB |
Output is correct |
| 35 |
Correct |
0 ms |
604 KB |
Output is correct |
| 36 |
Correct |
0 ms |
604 KB |
Output is correct |
| 37 |
Correct |
0 ms |
468 KB |
Output is correct |
| 38 |
Correct |
0 ms |
604 KB |
Output is correct |
| 39 |
Correct |
1 ms |
608 KB |
Output is correct |
| 40 |
Correct |
0 ms |
604 KB |
Output is correct |
| 41 |
Correct |
1 ms |
612 KB |
Output is correct |
| 42 |
Correct |
0 ms |
608 KB |
Output is correct |
| 43 |
Correct |
1 ms |
608 KB |
Output is correct |
| 44 |
Correct |
1 ms |
612 KB |
Output is correct |
| 45 |
Correct |
0 ms |
608 KB |
Output is correct |
