# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
474772 | Duy_e | Palindrome-Free Numbers (BOI13_numbers) | C++14 | 3 ms | 460 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>
#define ll long long
#define ull unsigned long long
#define pii pair<long long, long long>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long oo = 1e18;
const long long N = 2e5 + 5;
ll dp[20][11][11][2][2];
vector <int> num;
ll cal(int pos, int pre, int cur, bool f, bool lz){
if (pos == num.size()) return 1;
ll &ans = dp[pos][pre][cur][f][lz];
if (ans != - 1) return ans;
ans = 0;
ll lmt = num[pos];
if (f) lmt = 9;
for (int i = 0; i <= lmt; i ++)
if (i != pre && i != cur){
bool new_f = f, new_lz = lz & (i == 0);
int new_pre, new_cur;
if (f == 0 && i < lmt) new_f = 1;
if (new_lz) new_pre = new_cur = 10;
else {
new_cur = i;
if (lz) new_pre = 10; else new_pre = cur;
}
ans += cal(pos + 1, new_pre, new_cur, new_f, new_lz);
}
return ans;
}
ll solve(ll n){
memset(dp, -1, sizeof dp);
if (n <= 0) return 0;
num.clear();
while (n > 0) num.push_back(n%10), n/=10;
reverse(num.begin(), num.end());
return cal(0, 10, 10, 0, 1);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
#endif
ll A, B;
cin >> A >> B;
cout << solve(B) - solve(A - 1);
return 0;
}
/** /\_/\
* (= ._.)
* / >0 \>1
**/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |