oj.uz

Submission #1113934

# Submission time Handle Problem Language Result Execution time Memory
1113934 2024-11-17T21:05:19 Z NoMercy Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 22, MAXM = 10;
ll dp[MAXN][MAXM][MAXM][2];
ll get (ll x) {
    string v = to_string(x);
    if (x < 10) return 1LL + x;
    for (int i = 0;i < MAXN;i ++) {
        for (int j = 0;j < MAXM;j ++) {
            for (int k = 0;k < MAXM;k ++) {
                dp[i][j][k][0] = dp[i][j][k][1] = 0;
            }
        }
    }

    int N = v.size();
    reverse (v.begin(), v.end());
    // for (auto x : v) cout << x << " ";
    // cout << "\n";

    ll ans = 10;
    for (int a = 0;a < MAXM;a ++) {
        for (int b = 0;b < MAXM;b ++) {
            if (a == b) continue;
            if ((a < (v[1] - '0')) || (a <= (v[1] - '0') && b <= (v[0] - '0'))) {
                dp[1][a][b][0] ++;
            } else {
                dp[1][a][b][1] ++;
            }
        }
    }
    for (int i = 2;i < N;i ++) {
        for (int a = 0;a < MAXM;a ++) {
            for (int b = 0;b < MAXM;b ++) {
                for (int c = 0;c < MAXM;c ++) {
                    if ((a == b) || (b == c) || (a == c)) continue;
                    if (a < (v[i] - '0')) {
                        dp[i][a][b][0] += dp[i - 1][b][c][0] + dp[i - 1][b][c][1];
                    } else if (a == (v[i] - '0')) {
                        dp[i][a][b][0] += dp[i - 1][b][c][0];
                        dp[i][a][b][1] += dp[i - 1][b][c][1];
                    } else {
                        dp[i][a][b][1] += dp[i - 1][b][c][0] + dp[i - 1][b][c][1];
                    }
                }
            }
        }
    }
    // for (int i = 1;i < N;i ++) {
    //     for (int x = 0;x < 10;x ++) {
    //         for (int y = 0;y < 10;y ++) {
    //             cout << dp[i][x][y][0] << " " << dp[i][x][y][1] << " | ";
    //         } cout << "\n";
    //     } cout << "\n";
    // } cout << "\n";
    for (int i = 1;i < N;i ++) {
        for (int a = 1;a < MAXM;a ++) {
            for (int b = 0;b < MAXM;b ++) if (a != b) {
                ans += dp[i][a][b][0];
                if (i != N - 1) ans += dp[i][a][b][1];
            }
        }
    }
    return ans;
};

int check (ll x) {
    string v = to_string(x);
    reverse (v.begin(), v.end());
    for (int i = 1;i < v.size();i ++) if (v[i - 1] == v[i]) return 0;
  for (int i = 2;i < v.size();i ++) if (v[i - 2] == v[i]) return 0;
    return 1;
}

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    ll A, B;
    cin >> A >> B;
    // cout << A << " " << B << "\n";
    ll ans = get (B) - get (A) + check (A);
    // cout << get (to_string(B)) << " " << get (to_string(A)) << " " << check (to_string(A)) << "\n";
    cout << ans << "\n";
}

Compilation message

numbers.cpp: In function 'int check(ll)':
numbers.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 1;i < v.size();i ++) if (v[i - 1] == v[i]) return 0;
      |                    ~~^~~~~~~~~~
numbers.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int i = 2;i < v.size();i ++) if (v[i - 2] == v[i]) return 0;
      |                  ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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