제출 #1311090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311090		chithanhnguyen	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	2 ms	620 KiB

numbers

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

#define int long long

const int MAXD = 20;
int x[MAXD];
int dp[MAXD][2][11][11][2];

int f(int idx, bool smaller, int prev_digit, int prev_digit2, bool leading_zero) {
    if (idx < 0) return 1;

    int &memo = dp[idx][smaller][prev_digit + 1][prev_digit2 + 1][leading_zero];
    if (memo != -1) return memo;

    int lim = (smaller ? 9 : x[idx]);
    memo = 0;

    for (int d = 0; d <= lim; ++d) {
        bool new_smaller = smaller || (d < lim);
        bool new_leading_zero = leading_zero && (d == 0);

        if (d == prev_digit || d == prev_digit2) continue;

        memo += f(idx - 1, new_smaller, new_leading_zero ? -1 : d, prev_digit, new_leading_zero);
    }

    return memo;
}

int g(int num) {
    if (num < 0) return 0;
    int n = 0;
    while (num > 0) {
        x[n++] = num % 10;
        num /= 10;
    }

    memset(dp, -1, sizeof dp);
    return f(n - 1, false, -1, -1, true);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    int a, b; cin >> a >> b;
    cout << g(b) - g(a - 1);

    return 0;
}

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