Submission #593315

#	Time	Username	Problem	Language	Result	Execution time	Memory
593315		bogdanvladmihai	Palindrome-Free Numbers (BOI13_numbers)	C++17	71.25 / 100	1 ms	568 KiB

numbers

#include <bits/stdc++.h>
using namespace std;

/***
Count the number of ways from 0 to N such that:
* no two digits are the same
* there is no palindrome of lenght three inside it

***/

const int MAXL = 25;

long long dp[MAXL][MAXL][MAXL][2];
bool calculated[MAXL][MAXL][MAXL][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, const vector<int> &v) {
    if (i == (int)v.size()) {
        calculated[i][befLast][last][smaller] = true;
        dp[i][befLast][last][smaller] = 1;

        return dp[i][befLast][last][smaller];
    }
    if (calculated[i][befLast][last][smaller]) {
        return dp[i][befLast][last][smaller];
    }

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

        ans += f(i + 1, last, d, nxtSmall, v);
    }

    dp[i][befLast][last][smaller] = ans;
    calculated[i][befLast][last][smaller] = true;
    return ans;
}

long long solve(long long n) {
    if (n <= 10) {
        return 0;
    }

    memset(dp, 0, sizeof dp);
    memset(calculated, false, sizeof calculated);

    auto digits = getDigits(n);
    return f(0, 11, 12, false, digits);
}

int main() {
    long long a, b; cin >> a >> b;

    cout << solve(b) - solve(a - 1) << "\n";

    return 0;
}

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