#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dig[20];
ll dp[20][11][11][2][2]; //place, 2, 1, under, hasStarted
int f(int len, int d1, int d2, bool under, bool started) {
if (len == -1) return 1;
ll& res = dp[len][d1][d2][under][started];
if (res >= 0) return res;
res = 0;
if (under) {
if (d1 != 0 && d2 != 0) res += f(len-1,d2,started?0:10,under,started);
for (int d = 1; d <= 9; d++) {
if (d == d1 || d == d2) continue;
res += f(len-1,d2,d,under,true);
}
}
else {
if (dig[len] > 0 && d1 != 0 && d2 != 0) res += f(len-1,d2,started?0:10,true,started);
for (int d = 1; d < dig[len]; d++) {
if (d == d1 || d == d2) continue;
res += f(len-1,d2,d,true,true);
}
if (dig[len] != d1 && dig[len] != d2)
res += f(len-1,d2,dig[len],false,true);
}
//printf("[%d][%d][%d][%d]: %d\n",len,d1,d2,under,res);
return res;
}
ll solve(ll x) {
if (x == -1) return 0;
memset(dp,-1,sizeof dp);
int len = 0;
while (x) {
dig[len++] = x % 10;
x /= 10;
}
return f(len-1,10,10,false,false);
}
bool isPalindrome(ll x) {
vector<int> digits;
while (x > 0) {
digits.push_back(x % 10);
x /= 10;
}
if (digits.size() <= 1) return false;
for (int i = 0; i < digits.size()-1; i++) {
if (digits[i] == digits[i+1]) return true;
}
for (int i = 0; i < digits.size()-2; i++) {
if (digits[i] == digits[i+2]) return true;
}
return false;
}
ll check(ll x) {
ll ans = 0;
for (ll i = 0; i <= x; i++) {
if (!isPalindrome(i)) {
ans++;
//cout << i << '\n';
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll a, b; cin >> a >> b;
cout << (solve(b) - solve(a-1)) << '\n';
//cout << solve(a) << '\n';
/*
ll a; cin >> a;
cout << solve(a) << ' ' << check(a) << '\n';
*/
}
Compilation message
numbers.cpp: In function 'bool isPalindrome(ll)':
numbers.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < digits.size()-1; i++) {
~~^~~~~~~~~~~~~~~~~
numbers.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < digits.size()-2; i++) {
~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
0 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
380 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
3 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
380 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
0 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
12 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 24 |
Correct |
2 ms |
376 KB |
Output is correct |
| 25 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 26 |
Incorrect |
2 ms |
448 KB |
Output isn't correct |
| 27 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 28 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 29 |
Correct |
2 ms |
376 KB |
Output is correct |
| 30 |
Correct |
2 ms |
376 KB |
Output is correct |
| 31 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 32 |
Correct |
2 ms |
376 KB |
Output is correct |
| 33 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 34 |
Correct |
2 ms |
348 KB |
Output is correct |
| 35 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 36 |
Incorrect |
3 ms |
352 KB |
Output isn't correct |
| 37 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 38 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 39 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 40 |
Correct |
2 ms |
376 KB |
Output is correct |
| 41 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 42 |
Correct |
2 ms |
376 KB |
Output is correct |
| 43 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 44 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 45 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
