#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
int a, b;
int dp[21][2][2][11][11];
string Convert(int a)
{
string s;
if(a == 0) return "0";
while(a > 0)
{
s += a % 10 + '0';
a /= 10;
}
reverse(s.begin(), s.end());
return s;
}
int DP(int pos, bool prefix, bool allz, int last2, int last1)
{
if(~dp[pos][prefix][allz][last1][last2]) return dp[pos][prefix][allz][last1][last2];
if(pos == s.length()) return 1;
int limit;
if(prefix) limit = s[pos] - '0';
else limit = 9;
int ans = 0;
for(int d = 0; d <= limit; d++)
{
int digit;
if(d == 0 && allz) digit = 10;
else digit = d;
if(digit != 10 && digit == last1) continue;
if(digit != 10 && digit == last2) continue;
ans += DP(pos + 1, prefix && d == limit, allz && d == 0, last1, d);
}
return dp[pos][prefix][allz][last1][last2] = ans;
}
int Get()
{
fill_n(&dp[0][0][0][0][0], 21 * 2 * 2 * 11 * 11, -1);
return DP(0, 1, 1, 10, 10);
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
cin >> a >> b;
s = Convert(a - 1);
int ans1 = Get();
s = Convert(b);
int ans2 = Get();
if(a == 0) ans2++;
cout << ans2 - ans1;
}
Compilation message
numbers.cpp: In function 'long long int DP(long long int, bool, bool, long long int, long long int)':
numbers.cpp:26:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(pos == s.length()) return 1;
~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
524 KB |
Output isn't correct |
| 3 |
Correct |
2 ms |
584 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 9 |
Correct |
2 ms |
600 KB |
Output is correct |
| 10 |
Correct |
2 ms |
600 KB |
Output is correct |
| 11 |
Correct |
2 ms |
600 KB |
Output is correct |
| 12 |
Correct |
2 ms |
600 KB |
Output is correct |
| 13 |
Correct |
3 ms |
600 KB |
Output is correct |
| 14 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 16 |
Correct |
2 ms |
600 KB |
Output is correct |
| 17 |
Correct |
2 ms |
600 KB |
Output is correct |
| 18 |
Correct |
2 ms |
600 KB |
Output is correct |
| 19 |
Correct |
2 ms |
660 KB |
Output is correct |
| 20 |
Incorrect |
2 ms |
660 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
660 KB |
Output is correct |
| 4 |
Correct |
3 ms |
660 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
720 KB |
Output isn't correct |
| 6 |
Correct |
3 ms |
736 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
736 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
736 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
736 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
736 KB |
Output isn't correct |
| 11 |
Correct |
2 ms |
736 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
736 KB |
Output isn't correct |
| 13 |
Incorrect |
3 ms |
736 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
748 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
748 KB |
Output isn't correct |
| 16 |
Correct |
3 ms |
748 KB |
Output is correct |
| 17 |
Correct |
3 ms |
748 KB |
Output is correct |
| 18 |
Correct |
2 ms |
748 KB |
Output is correct |
| 19 |
Correct |
2 ms |
748 KB |
Output is correct |
| 20 |
Correct |
3 ms |
748 KB |
Output is correct |
| 21 |
Correct |
3 ms |
748 KB |
Output is correct |
| 22 |
Correct |
3 ms |
748 KB |
Output is correct |
| 23 |
Correct |
3 ms |
748 KB |
Output is correct |
| 24 |
Correct |
3 ms |
748 KB |
Output is correct |
| 25 |
Correct |
3 ms |
748 KB |
Output is correct |
| 26 |
Correct |
2 ms |
748 KB |
Output is correct |
| 27 |
Correct |
3 ms |
748 KB |
Output is correct |
| 28 |
Correct |
2 ms |
748 KB |
Output is correct |
| 29 |
Correct |
3 ms |
748 KB |
Output is correct |
| 30 |
Correct |
3 ms |
748 KB |
Output is correct |
| 31 |
Correct |
2 ms |
748 KB |
Output is correct |
| 32 |
Correct |
2 ms |
748 KB |
Output is correct |
| 33 |
Correct |
2 ms |
748 KB |
Output is correct |
| 34 |
Correct |
3 ms |
748 KB |
Output is correct |
| 35 |
Correct |
2 ms |
748 KB |
Output is correct |
| 36 |
Correct |
2 ms |
748 KB |
Output is correct |
| 37 |
Correct |
2 ms |
748 KB |
Output is correct |
| 38 |
Correct |
3 ms |
748 KB |
Output is correct |
| 39 |
Correct |
3 ms |
748 KB |
Output is correct |
| 40 |
Correct |
2 ms |
748 KB |
Output is correct |
| 41 |
Correct |
3 ms |
748 KB |
Output is correct |
| 42 |
Correct |
2 ms |
748 KB |
Output is correct |
| 43 |
Correct |
3 ms |
748 KB |
Output is correct |
| 44 |
Correct |
2 ms |
748 KB |
Output is correct |
| 45 |
Correct |
2 ms |
748 KB |
Output is correct |
