#include <bits/stdc++.h>
using namespace std;
#define task "PALINFREE"
#define fi first
#define se second
#define pii pair <int, int>
#define pb push_back
#define ll long long
#define pip pair <int, pii>
#define pli pair <ll, int>
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
long long a, b, f[25][5][5][15][15];
int n;
string s;
int myabs(int x)
{
return x < 0 ? -x : x;
}
void inp()
{
cin >> a;
cin >> b;
}
long long dp(int k, int st, int small, int pre1, int pre2)
{
if (k == n)
return 1;
if (f[k][st][small][pre1][pre2] != -1)
return f[k][st][small][pre1][pre2];
long long ans = 0;
int lim = 9;
if (small)
lim = s[k] - '0';
//cout << s[k] << " " << lim << endl;
for (int i=0; i<=lim; ++i)
{
if (i == pre1 || i == pre2)
continue;
int new_small = (small && i == lim);
int new_start = (st || i != 0);
if (new_start)
ans += dp(k + 1, new_start, new_small, i, pre1);
else ans += dp(k + 1, new_start, new_small, 10, 10);
}
//cout << k << " " << st << " " << small << " " << pre1 << " " << pre2 << " " << ans << endl;
return (f[k][st][small][pre1][pre2] = ans);
}
long long calc(long long a)
{
for (int i=0; i<20; ++i)
for (int j=0; j<2; ++j)
for (int x=0; x<2; ++x)
for (int y=0; y<11; ++y)
for (int z=0; z <11; ++z)
f[i][j][x][y][z] = -1;
s = to_string(a);
n = (int)s.size();
//cout << s << " " << n << endl;
return dp(0, 1, 1, 10, 10);
}
void solve()
{
cout << calc(b) - calc(a-1) << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
inp();
solve();
return 0;
}
Compilation message
numbers.cpp: In function 'int main()':
numbers.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
764 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 9 |
Correct |
1 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
592 KB |
Output is correct |
| 11 |
Correct |
2 ms |
848 KB |
Output is correct |
| 12 |
Correct |
1 ms |
592 KB |
Output is correct |
| 13 |
Correct |
1 ms |
592 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 15 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 16 |
Correct |
1 ms |
592 KB |
Output is correct |
| 17 |
Correct |
1 ms |
592 KB |
Output is correct |
| 18 |
Correct |
1 ms |
592 KB |
Output is correct |
| 19 |
Correct |
1 ms |
592 KB |
Output is correct |
| 20 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
592 KB |
Output is correct |
| 3 |
Correct |
2 ms |
592 KB |
Output is correct |
| 4 |
Correct |
1 ms |
592 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 6 |
Correct |
2 ms |
592 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 11 |
Correct |
1 ms |
592 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 13 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 15 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 16 |
Correct |
1 ms |
592 KB |
Output is correct |
| 17 |
Correct |
1 ms |
592 KB |
Output is correct |
| 18 |
Correct |
1 ms |
592 KB |
Output is correct |
| 19 |
Correct |
1 ms |
592 KB |
Output is correct |
| 20 |
Correct |
1 ms |
592 KB |
Output is correct |
| 21 |
Correct |
1 ms |
592 KB |
Output is correct |
| 22 |
Correct |
1 ms |
592 KB |
Output is correct |
| 23 |
Correct |
1 ms |
764 KB |
Output is correct |
| 24 |
Correct |
1 ms |
592 KB |
Output is correct |
| 25 |
Correct |
1 ms |
592 KB |
Output is correct |
| 26 |
Correct |
2 ms |
604 KB |
Output is correct |
| 27 |
Correct |
1 ms |
592 KB |
Output is correct |
| 28 |
Correct |
1 ms |
760 KB |
Output is correct |
| 29 |
Correct |
1 ms |
592 KB |
Output is correct |
| 30 |
Correct |
1 ms |
592 KB |
Output is correct |
| 31 |
Correct |
1 ms |
592 KB |
Output is correct |
| 32 |
Correct |
1 ms |
592 KB |
Output is correct |
| 33 |
Correct |
1 ms |
592 KB |
Output is correct |
| 34 |
Correct |
1 ms |
592 KB |
Output is correct |
| 35 |
Correct |
1 ms |
592 KB |
Output is correct |
| 36 |
Correct |
1 ms |
592 KB |
Output is correct |
| 37 |
Correct |
2 ms |
652 KB |
Output is correct |
| 38 |
Correct |
1 ms |
760 KB |
Output is correct |
| 39 |
Correct |
1 ms |
592 KB |
Output is correct |
| 40 |
Correct |
1 ms |
592 KB |
Output is correct |
| 41 |
Correct |
1 ms |
592 KB |
Output is correct |
| 42 |
Correct |
1 ms |
592 KB |
Output is correct |
| 43 |
Correct |
2 ms |
592 KB |
Output is correct |
| 44 |
Correct |
1 ms |
592 KB |
Output is correct |
| 45 |
Correct |
1 ms |
592 KB |
Output is correct |
