# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
57378 | RezwanArefin01 | Palindrome-Free Numbers (BOI13_numbers) | C++17 | 4 ms | 704 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
ll dp[20][11][11][2][2];
string s;
ll f(int pos, int a, int b, bool small, bool start) {
if(pos == s.size()) return 1;
ll &ret = dp[pos][a][b][small][start];
if(~ret) return ret;
ret = 0;
int lim = small ? 9 : s[pos] - '0';
for(int i = 0; i <= lim; i++) {
if(i == a || i == b) continue;
if(!i && start) {
ret += f(pos + 1, 10, 10, 1, 1);
} else {
ret += f(pos + 1, b, i, small | (i < lim), 0);
}
} return ret;
}
ll solve(ll n) {
s = to_string(n);
memset(dp, -1, sizeof dp);
return f(0, 10, 10, 0, 1);
}
int main(int argc, char const *argv[]) {
ll a, b;
scanf("%lld %lld", &a, &b);
ll ans = solve(b);
if(a) ans -= solve(a - 1);
printf("%lld\n", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |