oj.uz

Submission #593322

# Submission time Handle Problem Language Result Execution time Memory
593322 2022-07-10T21:16:41 Z bogdanvladmihai Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 1 ms 852 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXL = 25;

long long dp[MAXL][MAXL][MAXL][2][2];
bool calculated[MAXL][MAXL][MAXL][2][2];

vector<int> getDigits(long long n) {
    vector<int> v;

    do {
        v.push_back(n % 10);
        n /= 10;
    } while (n > 0);
    reverse(v.begin(), v.end());

    return v;
}

long long f(int i, int befLast, int last, bool smaller, bool nonZero, const vector<int> &v) {
    if (i == (int)v.size()) {
        calculated[i][befLast][last][smaller][nonZero] = true;
        dp[i][befLast][last][smaller][nonZero] = 1;

        return dp[i][befLast][last][smaller][nonZero];
    }
    if (calculated[i][befLast][last][smaller][nonZero]) {
        return dp[i][befLast][last][smaller][nonZero];
    }

    long long ans = 0;

    int l = v[i];
    if (smaller) {
        l = 9;
    }
    for (int d = 0; d <= l; d++) {
        if (d == last || d == befLast) {
            continue;
        }

        bool nxtSmall = true;
        if (!smaller && d == l) {
            nxtSmall = false;
        }
        bool nZero = nonZero | (d > 0);

        int lst = last, curr = d;
        if (d == 0 && !nonZero) {
            lst = 10;
            curr = 10;
        }

        ans += f(i + 1, lst, curr, nxtSmall, nZero, v);
    }

    dp[i][befLast][last][smaller][nonZero] = ans;
    calculated[i][befLast][last][smaller][nonZero] = true;
    return ans;
}

long long solve(long long n) {
    if (n <= 10) {
        return (n == -1 ? 0 : n + 1);
    }

    memset(dp, 0, sizeof dp);
    memset(calculated, false, sizeof calculated);

    auto digits = getDigits(n);
    return f(0, 10, 10, false, false, digits);
}

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

    cout << solve(b) - solve(a - 1) << "\n";

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 852 KB Output is correct
2 Correct 0 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 852 KB Output is correct
7 Correct 0 ms 852 KB Output is correct
8 Correct 0 ms 852 KB Output is correct
9 Correct 0 ms 852 KB Output is correct
10 Correct 0 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 0 ms 852 KB Output is correct
13 Correct 0 ms 852 KB Output is correct
14 Correct 0 ms 852 KB Output is correct
15 Correct 0 ms 852 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 832 KB Output is correct
20 Correct 1 ms 852 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 852 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 1 ms 852 KB Output is correct
22 Correct 1 ms 852 KB Output is correct
23 Correct 1 ms 852 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 1 ms 852 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 1 ms 852 KB Output is correct
28 Correct 1 ms 852 KB Output is correct
29 Correct 1 ms 852 KB Output is correct
30 Correct 1 ms 852 KB Output is correct
31 Correct 1 ms 852 KB Output is correct
32 Correct 1 ms 852 KB Output is correct
33 Correct 1 ms 852 KB Output is correct
34 Correct 1 ms 852 KB Output is correct
35 Correct 1 ms 752 KB Output is correct
36 Correct 1 ms 852 KB Output is correct
37 Correct 1 ms 852 KB Output is correct
38 Correct 1 ms 852 KB Output is correct
39 Correct 1 ms 852 KB Output is correct
40 Correct 1 ms 852 KB Output is correct
41 Correct 1 ms 852 KB Output is correct
42 Correct 1 ms 852 KB Output is correct
43 Correct 1 ms 852 KB Output is correct
44 Correct 1 ms 852 KB Output is correct
45 Correct 1 ms 724 KB Output is correct