#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin(),(x).end())
#define len(x) ((int)(x).size())
const int N = 19;
ll dp[N][11][11];
ll tot[N];
void init(){
for(int i = 0;i < 10; i ++ )
dp[1][i][i] = 1;
tot[1] = 10;
tot[2] = 9 * 9;
for(int i = 0; i < 10; i ++ ){
for(int j = 0;j < 10; j ++ ){
if(i != j and i > 0)
dp[2][i][j] = 1;
}
}
for(int num = 2; num < N - 1; num ++ ){
for(int x = 0; x < 10; x ++ ){
for(int z = 0;z < 10; z ++ ){
for(int nx = 0; nx < 10; nx ++ ){
if(nx != z and nx != x){
dp[num + 1][z][nx] += dp[num][x][z];
tot[num + 1] += dp[num + 1][z][nx];
}
}
}
}
}
}
ll calc(ll x){
if(x == -1)
return 0;
vector<int> idx;
do{
idx.push_back(x % 10);
x /= 10;
}while(x > 0);
if(idx.size() == 1)
return idx[0] + 1;
if(idx.size() == 2){
ll ans = 10;
for(int y = 0; y < 10; y ++ ){
for(int z = 0; z < 10; z ++ ){
if(y > 0 and y != z and y * 10 + z <= idx[0] * 10 + idx[1]){
ans ++ ;
}
}
}
return ans;
}
reverse(idx.begin(), idx.end());
ll ans = tot[1];
ll dp2[20][10][10][2];
memset(dp2, 0, sizeof dp2);
for(int y = 0 ; y < 10; y ++ ){
for(int z = 0; z < 10 ; z ++ ){
if(y != 0 and y != z and y * 10 + z <= idx[0] * 10 + idx[1]){
dp2[2][y][z][(y * 10 + z) != (idx[0] * 10 + idx[1])] ++;
}
}
}
int p = 3;
for(auto xx : idx){
ans += tot[p - 1];
for(int y = 0; y < 10; y ++ ){
for(int z = 0; z < 10 ; z ++ ){
for(int nx = 0; nx < 10; nx ++ ){
if(y != nx and z != nx){
if(nx > xx){
dp2[p][z][nx][1] += dp2[p - 1][y][z][1];
}
else if(nx < xx){
dp2[p][z][nx][1] += dp2[p - 1][y][z][0] + dp2[p - 1][y][z][1];
}
else{
dp2[p][z][nx][0] += dp2[p - 1][y][z][0];
dp2[p][z][nx][1] += dp2[p - 1][y][z][1];
}
}
}
}
}
p ++ ;
}
for(int y = 0; y < 10; y ++ ){
for(int z = 0; z < 10; z ++ ){
ans += dp2[idx.size()][y][z][0] + dp2[idx.size()][y][z][1];
}
}
return ans;
}
int main(){
fastIO;
init();
ll a, b;
cin >> a >> b;
cout << calc(b) - calc(a - 1);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
516 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
564 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
716 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
716 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
716 KB |
Output isn't correct |
| 13 |
Correct |
2 ms |
716 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
716 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
772 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
792 KB |
Output isn't correct |
| 17 |
Incorrect |
2 ms |
792 KB |
Output isn't correct |
| 18 |
Correct |
2 ms |
792 KB |
Output is correct |
| 19 |
Incorrect |
2 ms |
792 KB |
Output isn't correct |
| 20 |
Incorrect |
2 ms |
792 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
792 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
824 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 17 |
Correct |
2 ms |
840 KB |
Output is correct |
| 18 |
Correct |
2 ms |
840 KB |
Output is correct |
| 19 |
Correct |
2 ms |
840 KB |
Output is correct |
| 20 |
Correct |
2 ms |
840 KB |
Output is correct |
| 21 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 22 |
Correct |
2 ms |
840 KB |
Output is correct |
| 23 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 24 |
Correct |
2 ms |
840 KB |
Output is correct |
| 25 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 26 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 27 |
Incorrect |
2 ms |
840 KB |
Output isn't correct |
| 28 |
Incorrect |
2 ms |
848 KB |
Output isn't correct |
| 29 |
Correct |
2 ms |
848 KB |
Output is correct |
| 30 |
Correct |
2 ms |
848 KB |
Output is correct |
| 31 |
Incorrect |
2 ms |
848 KB |
Output isn't correct |
| 32 |
Correct |
2 ms |
848 KB |
Output is correct |
| 33 |
Incorrect |
2 ms |
848 KB |
Output isn't correct |
| 34 |
Correct |
2 ms |
852 KB |
Output is correct |
| 35 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 36 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 37 |
Incorrect |
2 ms |
928 KB |
Output isn't correct |
| 38 |
Incorrect |
2 ms |
928 KB |
Output isn't correct |
| 39 |
Incorrect |
2 ms |
928 KB |
Output isn't correct |
| 40 |
Correct |
2 ms |
928 KB |
Output is correct |
| 41 |
Incorrect |
2 ms |
928 KB |
Output isn't correct |
| 42 |
Correct |
2 ms |
928 KB |
Output is correct |
| 43 |
Incorrect |
2 ms |
928 KB |
Output isn't correct |
| 44 |
Incorrect |
2 ms |
928 KB |
Output isn't correct |
| 45 |
Incorrect |
2 ms |
928 KB |
Output isn't correct |
