#include <algorithm>
#include <cstdio>
#include <vector>
#include <iostream>
#include <map>
#include <cstring>
#define LOCAL true
/*
Author: Oleksii Renov
*/
using namespace std;
using ll = long long int;
int dp[20][11][11][2][2];
ll run(int pos, int last1, int last2, bool smaller, bool started, const string& x) {
if (pos == x.size()) {
return 1;
}
if (dp[pos][last1][last2][smaller][started] != -1) {
return dp[pos][last1][last2][smaller][started];
}
int end = smaller ? 9 : (x[pos] - '0');
ll cnt = 0;
for (int i = 0; i <= end; ++i) {
if (!started && i == 0) continue;
if (i != last1 && i != last2) {
cnt += run(pos + 1, i, last1, smaller || (i != end), started || (i != 0), x);
}
}
dp[pos][last1][last2][smaller][started] = cnt;
return cnt;
}
int main() {
ll a, b;
cin >> a >> b;
memset(dp, -1, sizeof(dp));
ll cnt1 = run(0, 10, 10, false, false, to_string(b));
memset(dp, -1, sizeof(dp));
ll cnt2 = run(0, 10, 10, false, false, to_string(a-1));
std::cout << cnt1 - cnt2 << '\n';
}
Compilation message
numbers.cpp: In function 'll run(int, int, int, bool, bool, const string&)':
numbers.cpp:20:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | if (pos == x.size()) {
| ~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 15 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
0 ms |
340 KB |
Output is correct |
| 18 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 9 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 10 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 13 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 14 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 15 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
0 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 24 |
Correct |
0 ms |
340 KB |
Output is correct |
| 25 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 26 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 27 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 28 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
0 ms |
212 KB |
Output is correct |
| 31 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 32 |
Correct |
1 ms |
340 KB |
Output is correct |
| 33 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 34 |
Correct |
0 ms |
340 KB |
Output is correct |
| 35 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 36 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 37 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 38 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 39 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 40 |
Correct |
0 ms |
340 KB |
Output is correct |
| 41 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 42 |
Correct |
0 ms |
212 KB |
Output is correct |
| 43 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 44 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 45 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
