Submission #1211546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211546		i_love_spring	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	3 ms	1252 KiB

numbers

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

using ll = long long;

ll dp[20][2][2][11][11][11]; // pos, tight, leading_zero, last3 digits

string s;

bool has_palindrome(int a, int b, int c) {
    // a, b, c are last 3 digits
    // check for 2 or 3 length palindromes
    if (a != -1 && b != -1 && a == b) return true;        // "aa"
    if (b != -1 && c != -1 && b == c) return true;        // "bb"
    if (a != -1 && c != -1 && a == c) return true;        // "aba"
    return false;
}

ll dfs(int pos, bool tight, bool leading_zero, int a, int b, int c) {
    if (pos == s.size()) return 1;

    ll& res = dp[pos][tight][leading_zero][a + 1][b + 1][c + 1];
    if (res != -1) return res;

    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_zero = leading_zero && (d == 0);

        int na = b, nb = c, nc = d;
        if (new_leading_zero) {
            na = nb = nc = -1;
        }

        if (!new_leading_zero && has_palindrome(na, nb, nc)) continue;

        res += dfs(pos + 1, new_tight, new_leading_zero, na, nb, nc);
    }

    return res;
}

ll count_palindrome_free_up_to(ll n) {
    if (n < 0) return 0;
    s = to_string(n);
    memset(dp, -1, sizeof(dp));
    return dfs(0, true, true, -1, -1, -1);
}

ll count_palindrome_free_range(ll a, ll b) {
    return count_palindrome_free_up_to(b) - count_palindrome_free_up_to(a - 1);
}

int main() {
    ll a, b;
    cin >> a >> b;
    cout << count_palindrome_free_range(a, b) << '\n';
    return 0;
}

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