#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
const int N = 10;
int dp[2 * N][N + 1][N + 1][2], len; // dp[pos][i][j][smaller] -> i sonrakine aktarılan 2 önceki, j -> sonrakine aktarılan 1 önceki eleman eğer i veya j 10 ise sonrakine eleman kısıtlaması aktarılmıyor (başlangıç)
string s;
inline int calc(int a){
if(a < 0) return 0ll;
memset(dp, 0, sizeof(dp));
dp[0][10][10][0] = 1;
s.clear();
while(a){
s += ('0' + a % 10);
a /= 10;
}
reverse(s.begin(), s.end());
len = sz(s) / 2 + (sz(s) & 1);
for(int pos = 0; pos < sz(s); pos++){
for(int i = 0; i <= 10; i++){
for(int j = 0; j <= 10; j++){
if(i == j && i != 10) continue;
for(int smaller = 0; smaller < 2; smaller++){
for(int num = 0; num < 10; num++){
if(num == i || num == j || (!smaller && num > s[pos] - '0')) continue;
dp[pos + 1][num][i][smaller || num < s[pos] - '0'] += dp[pos][i][j][smaller];
}
}
}
}
}
int ans = 0;
for(int i = 0; i <= 10; i++){
for(int j = 0; j <= 10; j++){
if(i == j) continue;
ans += dp[sz(s)][i][j][0] + dp[sz(s)][i][j][1];
}
}
return ans;
}
inline void solve(){
int a, b;
cin >> a >> b;
int vala = calc(a - 1), valb = calc(b);
int palnum = valb - vala;
cout << palnum << "\n";
return;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |