제출 #1240372

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240372		goodluck2020	Palindrome-Free Numbers (BOI13_numbers)	C++17	10.83 / 100	1 ms	328 KiB

numbers

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

string s;
ll dp[20][2][2][11][11]; // pos, tight, leading_zero, last1, last2

// Check nếu 3 chữ số liên tiếp tạo thành palindrome (ABA)
bool is_bad(int last2, int last1, int cur) {
    return (last2 == cur);
}

// Digit DP function
ll dfs(int pos, bool tight, bool leading_zero, int last1, int last2) {
    if (pos == s.size()) return 1; // hợp lệ

    ll &res = dp[pos][tight][leading_zero][last1][last2];
    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 = (leading_zero && d == 0);
        int new_last1 = (new_leading ? 10 : d);
        int new_last2 = (new_leading ? 10 : last1);

        if (is_bad(last2, last1, d) && !new_leading)
            continue;

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

    return res;
}

// Count số palindrome-free từ 0 đến x
ll count_palindrome_free(ll x) {
    s = to_string(x);
    memset(dp, -1, sizeof dp);
    return dfs(0, 1, 1, 10, 10); // 10: chưa có chữ số nào trước đó
}

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

    if (a > 0)
        cout << count_palindrome_free(b) - count_palindrome_free(a - 1) << endl;
    else
        cout << count_palindrome_free(b) << endl;

    return 0;
}

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