Submission #1336594

#TimeUsernameProblemLanguageResultExecution timeMemory
1336594sh_qaxxorov_571Palindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms344 KiB
#include <iostream>
#include <string>
#include <vector>
#include <cstring>

using namespace std;

typedef long long ll;

// dp[indeks][oldingi1][oldingi2][is_less][is_started]
ll dp[20][11][11][2][2];
string s;

ll solve(int idx, int p1, int p2, bool is_less, bool is_started) {
    if (idx == s.size()) return 1;
    if (dp[idx][p1][p2][is_less][is_started] != -1) 
        return dp[idx][p1][p2][is_less][is_started];

    ll ans = 0;
    int limit = is_less ? 9 : s[idx] - '0';

    for (int d = 0; d <= limit; d++) {
        // Palindrom sharti: yangi raqam d oldingi p1 yoki p2 ga teng bo'lmasligi kerak
        if (is_started && (d == p1 || d == p2)) continue;

        bool next_is_started = is_started || (d > 0);
        ans += solve(idx + 1, d, (is_started ? p1 : 10), is_less || (d < limit), next_is_started);
    }

    return dp[idx][p1][p2][is_less][is_started] = ans;
}

ll count_pal_free(ll n) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    s = to_string(n);
    memset(dp, -1, sizeof(dp));
    return solve(0, 10, 10, false, false);
}

int main() {
    ll a, b;
    if (!(cin >> a >> b)) return 0;
    
    // Natija: count(b) - count(a-1)
    cout << count_pal_free(b) - count_pal_free(a - 1) << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...