Submission #507515

#	Time	Username	Problem	Language	Result	Execution time	Memory
507515		magmag	Palindrome-Free Numbers (BOI13_numbers)	C++17	73.75 / 100	1 ms	332 KiB

numbers

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

int len;
string upper;

// len-1, len-2, ... ,0
// 0, 1, ... len-1
ll dp[19][2][10][10];

ll calc(int i = 0, bool touch = 1, int p = -1, int pp = -1) {
    if (i == len)return 1;

    if (dp[i][touch][p][pp] != -1)return dp[i][touch][p][pp];

    ll ret = 0;
    if (touch) {
        int uuu = upper[i] - '0';
        for (int d = 0; d <= uuu; ++d) {
            if (d == p || d == pp)continue;
            ret += calc(i+1, d == uuu, d, p);
        }
    } else {
        for (int d = 0; d < 10; ++d) {
            if (d == p || d == pp)continue;
            ret += calc(i+1, false, d, p);
        }
    }
    return dp[i][touch][p][pp] = ret;
}

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

    memset(dp, -1, sizeof dp);
    upper = to_string(b);
    len = upper.length();

    ll ans = calc();

    if (a > 1) {
        memset(dp, -1, sizeof dp);
        upper = to_string(a-1);
        len = upper.length();
        ans -= calc();
    }

    cout << ans << endl;

    return 0;
}

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