// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
ll dp[11][11][20], ans;
int L[20], R[20];
void inp(int *a){
ll x;
cin >> x;
for(int i = 0; i < 20; i++, x/=10)
a[i] = x % 10;
}
int a[20], frs = 19;
void go(int nw, bool yp, bool okL, bool okR){
if(okL && okR){
ans+= dp[(nw + 2 <= frs) ? a[nw+2] : 10][(nw + 1 <= frs) ? a[nw + 1] : 10][nw + 1];
return;
}
if(nw == -1){
ans++;
return;
}
if(!yp){
frs = nw;
}
for(int i = 0; i < 10; i++){
if(okL == 0 && i < L[nw])
continue;
if(okR == 0 && R[nw] < i)
continue;
if(nw + 1 <= frs && i == a[nw+1])
continue;
if(nw + 2 <= frs && i == a[nw+2])
continue;
a[nw] = i;
go(nw-1, yp || (i > 0), okL || (L[nw] < i), okR || (i < R[nw]));
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
for(int i = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
dp[i][j][0] = 1;
for(int i = 0; i < 10; i++)
dp[10][i][0] = 1;
dp[10][10][0] = 1;
for(int i = 1; i < 20; i++){
for(int j = 0; j <= 10; j++){
for(int k = 0; k <= 10; k++){
for(int w = 0; w < 10; w++){
if(k != w && j != w)
dp[j][k][i]+= dp[k][w][i-1];
}
}
}
}
inp(L), inp(R); // L = zero
go(19, 0, 0, 0);
return cout << ans << endl, 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Correct |
0 ms |
384 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 15 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 16 |
Correct |
0 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
0 ms |
384 KB |
Output is correct |
| 19 |
Correct |
0 ms |
384 KB |
Output is correct |
| 20 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 9 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 10 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 15 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
0 ms |
384 KB |
Output is correct |
| 19 |
Correct |
0 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
0 ms |
384 KB |
Output is correct |
| 22 |
Correct |
0 ms |
384 KB |
Output is correct |
| 23 |
Correct |
0 ms |
384 KB |
Output is correct |
| 24 |
Correct |
0 ms |
384 KB |
Output is correct |
| 25 |
Correct |
0 ms |
384 KB |
Output is correct |
| 26 |
Correct |
0 ms |
384 KB |
Output is correct |
| 27 |
Correct |
0 ms |
384 KB |
Output is correct |
| 28 |
Correct |
0 ms |
384 KB |
Output is correct |
| 29 |
Correct |
0 ms |
384 KB |
Output is correct |
| 30 |
Correct |
0 ms |
384 KB |
Output is correct |
| 31 |
Correct |
0 ms |
384 KB |
Output is correct |
| 32 |
Correct |
1 ms |
384 KB |
Output is correct |
| 33 |
Correct |
0 ms |
384 KB |
Output is correct |
| 34 |
Correct |
0 ms |
384 KB |
Output is correct |
| 35 |
Correct |
0 ms |
384 KB |
Output is correct |
| 36 |
Correct |
1 ms |
384 KB |
Output is correct |
| 37 |
Correct |
1 ms |
384 KB |
Output is correct |
| 38 |
Correct |
1 ms |
384 KB |
Output is correct |
| 39 |
Correct |
0 ms |
384 KB |
Output is correct |
| 40 |
Correct |
1 ms |
384 KB |
Output is correct |
| 41 |
Correct |
1 ms |
384 KB |
Output is correct |
| 42 |
Correct |
1 ms |
384 KB |
Output is correct |
| 43 |
Correct |
0 ms |
384 KB |
Output is correct |
| 44 |
Correct |
1 ms |
384 KB |
Output is correct |
| 45 |
Correct |
0 ms |
384 KB |
Output is correct |
