#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 998244353
#define INF 1000000001
#define LNF 1000000000000000001
#define int ll
#define MAX 100000
#define MAXLOG 17
#define int ll
typedef pair<int,int> pii;
pii bruh(int x){
pii ret = {1,1};
while(x > 9){
x/=10;
ret.first++;
ret.second *= 10;
}
return ret;
}
int powon[19];
int dp[19][2][11][11];
int pre(int x){
if(x < 0)
return 0;
for(int i = 0;i < 19;i++)
for(int j = 0;j < 2;j++)
for(int k = 0;k < 11;k++)
for(int l = 0;l < 11;l++)
dp[i][j][k][l] = 0;
pii cum = bruh(x);
dp[cum.first][1][10][10] = 1;
for(int i = cum.first;i >= 1;i--)
for(int j = 0;j < 2;j++)
for(int k = 0;k < 11;k++)
for(int l = 0;l < 11;l++){
if(dp[i][j][k][l] == 0)
continue;
int mx = 9;
if(j == 1){
mx = x/powon[i-1]%10;
}
int mn = 0;
if(k == 10 && i > 1)
mn = 1;
for(int m = mx;m >= mn;m--){
if(m != k && m != l){
int flag = j && (m == x/powon[i-1]%10);
dp[i-1][flag][m][k] += dp[i][j][k][l];
// cout << i-1 << ' ' << flag << ' ' << m << ' ' << k << '+' << dp[i][j][k][l] << '\n';
}
}
if(i > 1 && k == 10){
dp[i-1][0][10][k] += dp[i][j][k][l];
// cout << i-1 << ' ' << 0 << ' ' << 10 << ' ' << k << '+' << dp[i][j][k][l] << '\n';
}
}
int ret = 0;
for(int j = 0;j < 2;j++)
for(int k = 0;k < 10;k++)
for(int l = 0;l < 11;l++){
// if(dp[0][j][k][l] > 0)
// cout << 0 << ' ' << j << ' ' << k << ' ' << l << ' ' << dp[0][j][k][l] << '\n';
ret += dp[0][j][k][l];
}
return ret;
}
void solve(){
//#define TEST
int curr = 1;
for(int i = 0;i < 19;i++){
powon[i] = curr;
curr *= 10;
}
// for(int i = 1;i < 100000;i++){
// if(pre(i) != brute(i)){
// cout << i << ' ' << pre(i) << ' ' << brute(i) << '\n';
// }
// }
int a,b;cin >> a >> b;
// cout << a << ' ' << b << '\n';
cout << pre(b)-pre(a-1);
}
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
#ifdef DEBUG
freopen("i.txt","r",stdin);
freopen("o.txt","w",stdout);
#endif
int t = 1;
#ifdef TEST
cin >> t;
#endif
while(t--){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
308 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
316 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
2 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
316 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
296 KB |
Output is correct |
| 20 |
Correct |
1 ms |
304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
292 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
316 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
2 ms |
320 KB |
Output is correct |
| 13 |
Correct |
1 ms |
268 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
3 ms |
332 KB |
Output is correct |
| 19 |
Correct |
2 ms |
308 KB |
Output is correct |
| 20 |
Correct |
2 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
296 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
316 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
2 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
312 KB |
Output is correct |
| 27 |
Correct |
2 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| 30 |
Correct |
1 ms |
332 KB |
Output is correct |
| 31 |
Correct |
1 ms |
332 KB |
Output is correct |
| 32 |
Correct |
1 ms |
312 KB |
Output is correct |
| 33 |
Correct |
1 ms |
332 KB |
Output is correct |
| 34 |
Correct |
1 ms |
332 KB |
Output is correct |
| 35 |
Correct |
1 ms |
332 KB |
Output is correct |
| 36 |
Correct |
1 ms |
332 KB |
Output is correct |
| 37 |
Correct |
1 ms |
332 KB |
Output is correct |
| 38 |
Correct |
1 ms |
312 KB |
Output is correct |
| 39 |
Correct |
1 ms |
332 KB |
Output is correct |
| 40 |
Correct |
1 ms |
332 KB |
Output is correct |
| 41 |
Correct |
1 ms |
316 KB |
Output is correct |
| 42 |
Correct |
1 ms |
332 KB |
Output is correct |
| 43 |
Correct |
1 ms |
332 KB |
Output is correct |
| 44 |
Correct |
1 ms |
332 KB |
Output is correct |
| 45 |
Correct |
1 ms |
332 KB |
Output is correct |
