Submission #1287466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287466		dang_hai_long	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	2 ms	588 KiB

numbers

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

string S;
long long memo[20][2][11][11];
bool seen[20][2][11][11];

long long dfs(int pos, int started, int last1, int last2, int tight) {
    int L = (int)S.size();
    if (pos == L) {
        return 1;
    }
    if (!tight && seen[pos][started][last1][last2]) return memo[pos][started][last1][last2];
    int maxd = tight ? (S[pos]-'0') : 9;
    long long res = 0;
    for (int d = 0; d <= maxd; ++d) {
        int nstarted = started;
        int nlast1 = last1, nlast2 = last2;
        if (!started && d == 0) {
            nstarted = 0;
            res += dfs(pos+1, nstarted, nlast1, nlast2, tight && (d==maxd));
        } else {
            if (!started) {
                nstarted = 1;
                nlast1 = d;
                nlast2 = 10;
                res += dfs(pos+1, nstarted, nlast1, nlast2, tight && (d==maxd));
            } else {
                if (last1 != 10 && d == last1) continue;
                if (last2 != 10 && d == last2) continue;
                nlast2 = last1;
                nlast1 = d;
                res += dfs(pos+1, nstarted, nlast1, nlast2, tight && (d==maxd));
            }
        }
    }
    if (!tight) {
        seen[pos][started][last1][last2] = true;
        memo[pos][started][last1][last2] = res;
    }
    return res;
}

long long count_pf(unsigned long long X) {
    S = to_string(X);
    memset(seen, 0, sizeof(seen));
    return dfs(0, 0, 10, 10, 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unsigned long long a,b;
    if(!(cin >> a >> b)) return 0;
    unsigned long long ans;
    if (a == 0) {
        ans = count_pf(b);
    } else {
        ans = count_pf(b) - count_pf(a-1);
    }
    cout << ans << "\n";
    return 0;
}

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