Submission #1240373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240373		goodluck2020	Palindrome-Free Numbers (BOI13_numbers)	C++17	2.50 / 100	1099 ms	71260 KiB

numbers

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

string s;
map<tuple<int, bool, bool, string>, ll> memo;

// Hàm kiểm tra nếu một chuỗi là palindrome
bool is_palindrome(const string &s) {
    int l = 0, r = s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) return false;
        ++l; --r;
    }
    return true;
}

// Kiểm tra nếu vector chữ số hiện tại chứa substring palindrome dài ≥ 3
bool has_palindrome(const string &digits) {
    int n = digits.size();
    for (int len = 3; len <= n; ++len) {
        for (int i = 0; i + len <= n; ++i) {
            string sub = digits.substr(i, len);
            if (is_palindrome(sub))
                return true;
        }
    }
    return false;
}

// Digit DP
ll dfs(int pos, bool tight, bool leading_zero, string last_digits) {
    if (has_palindrome(last_digits)) return 0;  // không hợp lệ

    if (pos == s.size()) return 1; // hợp lệ

    auto key = make_tuple(pos, tight, leading_zero, last_digits);
    if (memo.count(key)) return memo[key];

    ll res = 0;
    int limit = tight ? s[pos] - '0' : 9;

    for (int d = 0; d <= limit; ++d) {
        bool new_tight = tight && (d == limit);
        bool new_leading = leading_zero && (d == 0);
        string new_last = last_digits;

        if (!new_leading) {
            new_last += (char)(d + '0');
            if (new_last.size() > 10) // chỉ giữ 10 chữ số cuối
                new_last.erase(0, 1);
        }

        res += dfs(pos + 1, new_tight, new_leading, new_last);
    }

    return memo[key] = res;
}

ll count_palindrome_free(ll x) {
    if (x < 0) return 0;
    s = to_string(x);
    memo.clear();
    return dfs(0, true, true, "");
}

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

    ll ans = count_palindrome_free(b) - count_palindrome_free(a - 1);
    cout << ans << "\n";

    return 0;
}

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