Submission #507515

#TimeUsernameProblemLanguageResultExecution timeMemory
507515magmagPalindrome-Free Numbers (BOI13_numbers)C++17
73.75 / 100
1 ms332 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...