Submission #593322

#	Time	Username	Problem	Language	Result	Execution time	Memory
593322		bogdanvladmihai	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	1 ms	852 KiB

numbers

#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;
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75