#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 = 1;i < 10; i ++ )
dp[1][i][i] = 1;
tot[1] = 9;
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 xy){
if(xy == -1)
return 0;
vector<int> idx;
while(xy > 0){
idx.push_back(xy % 10);
xy /= 10;
}
int dp2[20][10][10][2];
memset(dp2, 0, sizeof dp2);
int n = idx.size();
int las;
ll ans = 1;
for(int i = 1; i <= n; i ++ ){
las = idx.back();
idx.pop_back();
if(i != n)
ans += tot[i];
if(i == 1){
for(int nx = 1; nx <= las; nx ++ ){
dp2[i][nx][0][nx < las] = 1;
}
}
else if(i == 2){
for(int pv = 1; pv <= 9; pv ++ ){
for(int nx = 0; nx <= 9 ; nx ++ ){
if(pv != nx){
if(nx < las){
dp2[i][pv][nx][1] += dp2[i - 1][pv][0][0] + dp2[i - 1][pv][0][1];
}
else if(nx == las){
dp2[i][pv][nx][0] += dp2[i - 1][pv][0][0];
dp2[i][pv][nx][1] += dp2[i - 1][pv][0][1];
}
else{
dp2[i][pv][nx][1] += dp2[i - 1][pv][0][1];
}
}
}
}
}
else{
for(int y = 0 ; y <= 9; y ++ ){
for(int z = 0 ; z <= 9; z ++ ){
for(int nx = 0; nx < 10; nx ++ ){
if(nx == y or nx == z or y == z)
continue;
if(nx < las){
dp2[i][z][nx][1] += dp2[i - 1][y][z][0] + dp2[i - 1][y][z][1];
}
else if(nx == las){
dp2[i][z][nx][0] += dp2[i - 1][y][z][0];
dp2[i][z][nx][1] += dp2[i - 1][y][z][1];
}
else{
dp2[i][z][nx][1] += dp2[i - 1][y][z][1];
}
}
}
}
}
}
for(int y = 0; y <= 9; y ++ ){
for(int z = 0;z <= 9; z ++ ){
for(int d = 0; d < 2; d ++ ){
ans += dp2[n][y][z][d];
}
}
}
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 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
448 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
500 KB |
Output isn't correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
3 ms |
524 KB |
Output is correct |
| 7 |
Correct |
2 ms |
612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
612 KB |
Output is correct |
| 9 |
Correct |
2 ms |
612 KB |
Output is correct |
| 10 |
Correct |
2 ms |
612 KB |
Output is correct |
| 11 |
Correct |
2 ms |
632 KB |
Output is correct |
| 12 |
Correct |
2 ms |
636 KB |
Output is correct |
| 13 |
Correct |
2 ms |
640 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
804 KB |
Output isn't correct |
| 16 |
Correct |
2 ms |
804 KB |
Output is correct |
| 17 |
Correct |
2 ms |
804 KB |
Output is correct |
| 18 |
Correct |
2 ms |
804 KB |
Output is correct |
| 19 |
Correct |
3 ms |
804 KB |
Output is correct |
| 20 |
Incorrect |
2 ms |
804 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
804 KB |
Output is correct |
| 2 |
Correct |
2 ms |
804 KB |
Output is correct |
| 3 |
Correct |
2 ms |
804 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
804 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
804 KB |
Output isn't correct |
| 6 |
Correct |
2 ms |
804 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 11 |
Correct |
2 ms |
828 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
828 KB |
Output isn't correct |
| 16 |
Correct |
2 ms |
828 KB |
Output is correct |
| 17 |
Correct |
3 ms |
828 KB |
Output is correct |
| 18 |
Correct |
2 ms |
828 KB |
Output is correct |
| 19 |
Correct |
2 ms |
828 KB |
Output is correct |
| 20 |
Correct |
2 ms |
828 KB |
Output is correct |
| 21 |
Correct |
2 ms |
828 KB |
Output is correct |
| 22 |
Correct |
3 ms |
828 KB |
Output is correct |
| 23 |
Correct |
3 ms |
828 KB |
Output is correct |
| 24 |
Correct |
3 ms |
828 KB |
Output is correct |
| 25 |
Correct |
3 ms |
828 KB |
Output is correct |
| 26 |
Correct |
2 ms |
828 KB |
Output is correct |
| 27 |
Correct |
2 ms |
828 KB |
Output is correct |
| 28 |
Correct |
3 ms |
828 KB |
Output is correct |
| 29 |
Correct |
3 ms |
832 KB |
Output is correct |
| 30 |
Correct |
2 ms |
832 KB |
Output is correct |
| 31 |
Correct |
2 ms |
836 KB |
Output is correct |
| 32 |
Correct |
3 ms |
840 KB |
Output is correct |
| 33 |
Incorrect |
3 ms |
840 KB |
Output isn't correct |
| 34 |
Correct |
2 ms |
848 KB |
Output is correct |
| 35 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 36 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 37 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 38 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 39 |
Incorrect |
3 ms |
856 KB |
Output isn't correct |
| 40 |
Correct |
2 ms |
944 KB |
Output is correct |
| 41 |
Incorrect |
3 ms |
944 KB |
Output isn't correct |
| 42 |
Correct |
3 ms |
944 KB |
Output is correct |
| 43 |
Incorrect |
3 ms |
944 KB |
Output isn't correct |
| 44 |
Incorrect |
2 ms |
944 KB |
Output isn't correct |
| 45 |
Incorrect |
3 ms |
944 KB |
Output isn't correct |
