#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, x, y) for (int i = x; i < y; i++)
ll pw[19];
ll solve(ll val){
ll dp[2][2][10][10][2] = {}, ans = 0;
FOR(i, 0, 10) FOR(j, 0, 10) if (i != j or (i == 0 and j == 0)){
dp[1][(i*10+j <= val%100) ? 0 : 1][i][j][0]++;
}FOR(i, 2, 19){
memset(dp[0], 0, sizeof(dp[0])); ll dig = (val/pw[i])%10;
FOR(cmp, 0, 2) FOR(n1, 0, 10) FOR(n2, 0, 10) FOR(n3, 0, 2) FOR(j, 0, 10){
ll CMP = cmp; if (j < dig){CMP = 0;} if (j > dig){CMP = 1;}
if (j == 0 or (j != n1 and j != n2 and n1 != n2 and !(n3 == 1 and n1 == 0)))
dp[0][CMP][j][n1][(n2 == 0)] += dp[1][cmp][n1][n2][n3];
}swap(dp[0], dp[1]);
}FOR(i, 0, 10) FOR(j, 0, 10) FOR(k, 0, 2) ans += dp[1][0][i][j][k];
return ans;
}
int main(){
ll a, b; cin >> a >> b; pw[0] = 1; FOR(i, 1, 19) pw[i] = pw[i-1]*10;
cout<<solve(b)-solve(a-1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
288 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
288 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
2 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
288 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
288 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
2 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
2 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
2 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
292 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
1 ms |
296 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
2 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| 29 |
Correct |
2 ms |
204 KB |
Output is correct |
| 30 |
Correct |
1 ms |
288 KB |
Output is correct |
| 31 |
Correct |
1 ms |
204 KB |
Output is correct |
| 32 |
Correct |
1 ms |
204 KB |
Output is correct |
| 33 |
Correct |
1 ms |
204 KB |
Output is correct |
| 34 |
Correct |
1 ms |
204 KB |
Output is correct |
| 35 |
Correct |
1 ms |
204 KB |
Output is correct |
| 36 |
Correct |
1 ms |
204 KB |
Output is correct |
| 37 |
Correct |
2 ms |
204 KB |
Output is correct |
| 38 |
Correct |
1 ms |
204 KB |
Output is correct |
| 39 |
Correct |
1 ms |
204 KB |
Output is correct |
| 40 |
Correct |
1 ms |
292 KB |
Output is correct |
| 41 |
Correct |
1 ms |
204 KB |
Output is correct |
| 42 |
Correct |
1 ms |
204 KB |
Output is correct |
| 43 |
Correct |
1 ms |
204 KB |
Output is correct |
| 44 |
Correct |
1 ms |
288 KB |
Output is correct |
| 45 |
Correct |
1 ms |
204 KB |
Output is correct |
