oj.uz

Submission #546231

# Submission time Handle Problem Language Result Execution time Memory
546231 2022-04-06T17:30:59 Z _martynas Palindrome-Free Numbers (BOI13_numbers) C++11
100 / 100
 1 ms 308 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll solve(string a)
{
    // at i-th digit, last is d, before last is dd
    ll dp[20][11][11] = {};
    int n = a.size();
    bool hasPal = false;
    // take prefix + lower digit (or same at last turn)
    for(int i = 0; i < n; i++) {
        if(i)
        for(int d = 0; d <= 9; d++) {
            for(int dd = 0; dd <= 10; dd++) {
                if(dd == d) continue;
                for(int ddd = 0; ddd <= 10; ddd++) {
                    if(ddd == d) continue;
                    dp[i][d][dd] += dp[i-1][dd][ddd];
                }
            }
        }
        if(!hasPal) {
            for(int d = (i == 0); d < a[i]-'0' + (i == n-1); d++) {
                if((i >= 1 && d == a[i-1]-'0') || (i >= 2 && d == a[i-2]-'0')) {
                    continue;
                }
                dp[i][d][(i ? a[i-1]-'0' : 10)]++;
            }
        }
        if((i >= 1 && a[i] == a[i-1]) || (i >= 2 && a[i] == a[i-2])) {
            hasPal = true;
        }
    }

    ll ans = 0;
    for(int d = 0; d <= 9; d++)
    for(int dd = 0; dd <= 10; dd++)
        ans += dp[n-1][d][dd];

    return ans;
}

int main()
{
    string a, b;
    ll t;
    cin >> t >> b;
    t--;
    a = to_string(t);

    ll suma = 0, sumb;

    if(t > 0) {
        suma = solve(a);
        for(int i = 1; i < a.size(); i++) {
            suma += solve(string(i, '9'));
        }
        suma++; // 0
    }
    else if(t == 0) {
        suma++; // 0
    }

    sumb = solve(b);
    for(int i = 1; i < b.size(); i++) {
        sumb += solve(string(i, '9'));
    }
    sumb++; // 0
    cout << sumb - suma << "\n";
    return 0;
}
/*
10
99

11
22
33
44
55
66
77
88
99
= 9
90?

*/

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int i = 1; i < a.size(); i++) {
      |                        ~~^~~~~~~~~~
numbers.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 1; i < b.size(); i++) {
      |                    ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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