제출 #593316

#제출 시각아이디문제언어결과실행 시간메모리
593316bogdanvladmihaiPalindrome-Free Numbers (BOI13_numbers)C++14
71.25 / 100
1 ms468 KiB
#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;

unsigned long long dp[MAXL][MAXL][MAXL][2];
bool calculated[MAXL][MAXL][MAXL][2];

vector<int> getDigits(unsigned long long n) {
    vector<int> v;

    do {
        v.push_back(n % 10);
        n /= 10;
    } while (n > 0);
    reverse(v.begin(), v.end());

    return v;
}

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

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

unsigned long long solve(unsigned 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() {
    unsigned 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...