/**GreenGrass**/
#include <bits/stdc++.h>
#define Ford(i,a,b) for(int i=a;i>=b;--i)
#define Forr(i,a,b) for(int i=a;i<b;++i)
#define For(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;
int dp[22][10][10], f[22][10], q[22], top;
void Pre(){
For(i,1,9){
f[1][i] = 1;
f[2][i] = 9;
}
For(i,0,9)
For(j,0,9)
if(i!=j){
dp[2][i][j]=1;
}
For(le,3,19){
For(i,0,9){
For(j,0,9){
if(i==j) continue;
For(k,0,9){
if(i==k||j==k) continue;
dp[le][i][j] += dp[le-1][j][k];
}
f[le][i] += dp[le][i][j];
}
}
}
}
ll Calc(ll x){
if(x<=10) return x+1;
top = -1;
ll res = 1;
while(x){
q[++top] = x%10;
x/=10;
}
For(i,0,top-1)
For(j,1,9){
res += f[i+1][j];
}
q[top+1]=-1;
Ford(i,top,0){
For(j,0,q[i]-1){
if(q[i+1]==j) continue;
if(i==top&&!j) continue;
if(i<=top-2&&j==q[top+2]) continue;
if(i){
For(k,0,9){
if(k==q[i+1]||k==j) continue;
res += dp[i+1][j][k];
}
}
}
if(q[i+1]==q[i]) break;
if(i<=top-2&&q[i]==q[top+2]) break;
if(!i) ++res;
}
return res;
}
void Setup(){
ll a, b;
cin >> a >> b;
cout << Calc(b)-Calc(a-1);
}
int main(){
ios_base::sync_with_stdio(NULL);
cin .tie(NULL); cout .tie(NULL);
// freopen("BlaBla.inp" , "r", stdin);
// freopen("BlaBla.out", "w", stdout);
Pre();
Setup();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
508 KB |
Output isn't correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't 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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
380 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 20 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
380 KB |
Output is correct |
| 21 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 22 |
Correct |
2 ms |
380 KB |
Output is correct |
| 23 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 24 |
Correct |
2 ms |
376 KB |
Output is correct |
| 25 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 26 |
Incorrect |
2 ms |
304 KB |
Output isn't correct |
| 27 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 28 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 29 |
Correct |
2 ms |
376 KB |
Output is correct |
| 30 |
Correct |
2 ms |
376 KB |
Output is correct |
| 31 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 32 |
Correct |
2 ms |
376 KB |
Output is correct |
| 33 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 34 |
Correct |
2 ms |
376 KB |
Output is correct |
| 35 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 36 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 37 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 38 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 39 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 40 |
Correct |
2 ms |
376 KB |
Output is correct |
| 41 |
Incorrect |
2 ms |
296 KB |
Output isn't correct |
| 42 |
Correct |
2 ms |
376 KB |
Output is correct |
| 43 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 44 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 45 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
