Submission #596651

#TimeUsernameProblemLanguageResultExecution timeMemory
596651__joyboy__Palindrome-Free Numbers (BOI13_numbers)C++14
100 / 100
1 ms852 KiB
#include <bits/stdc++.h>
using namespace std;
 
const int MAXL = 25;
 
long long dp[MAXL][MAXL][MAXL][2][2];
bool calculated[MAXL][MAXL][MAXL][2][2];
 
vector<int> getDigits(long long n) {
    vector<int> v;
 
    do {
        v.push_back(n % 10);
        n /= 10;
    } while (n > 0);
    reverse(v.begin(), v.end());
 
    return v;
}
 
long long f(int i, int befLast, int last, bool smaller, bool nonZero, const vector<int> &v) {
    if (i == (int)v.size()) {
        calculated[i][befLast][last][smaller][nonZero] = true;
        dp[i][befLast][last][smaller][nonZero] = 1;
 
        return dp[i][befLast][last][smaller][nonZero];
    }
    if (calculated[i][befLast][last][smaller][nonZero]) {
        return dp[i][befLast][last][smaller][nonZero];
    }
 
    long long ans = 0;
 
    int l = v[i];
    if (smaller) {
        l = 9;
    }
    for (int d = 0; d <= l; d++) {
        if (d == last || d == befLast) {
            continue;
        }
 
        bool nxtSmall = true;
        if (!smaller && d == l) {
            nxtSmall = false;
        }
        bool nZero = nonZero | (d > 0);
 
        int lst = last, curr = d;
        if (d == 0 && !nonZero) {
            lst = 10;
            curr = 10;
        }
 
        ans += f(i + 1, lst, curr, nxtSmall, nZero, v);
    }
 
    dp[i][befLast][last][smaller][nonZero] = ans;
    calculated[i][befLast][last][smaller][nonZero] = true;
    return ans;
}
 
long long solve(long long n) {
    if (n <= 10) {
        return (n == -1 ? 0 : n + 1);
    }
 
    memset(dp, 0, sizeof dp);
    memset(calculated, false, sizeof calculated);
 
    auto digits = getDigits(n);
    return f(0, 10, 10, false, false, digits);
}
 
int main() {
    long long a, b; cin >> a >> b;
 
    cout << solve(b) - solve(a - 1) << "\n";
 
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...