oj.uz

답안 #1113920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1113920 2024-11-17T19:50:36 Z NoMercy Palindrome-Free Numbers (BOI13_numbers) C++17
90.8333 / 100
 2 ms 572 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 22, M = 10;
ll dp[N][M][M][2];
ll get (string v) {
    if (v.size() <= 1) return 1LL + (v[0] - '0');
    for (int i = 0;i < N;i ++) {
        for (int j = 0;j < M;j ++) {
            for (int k = 0;k < M;k ++) {
                dp[i][j][k][0] = dp[i][j][k][1] = 0;
            }
        }
    }

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

    ll ans = 10;
    for (int a = 0;a < M;a ++) {
        for (int b = 0;b < M;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 < v.size();i ++) {
        for (int a = 0;a < M;a ++) {
            for (int b = 0;b < M;b ++) {
                for (int c = 0;c < M;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 < v.size();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 < v.size();i ++) {
        for (int a = 1;a < M;a ++) {
            for (int b = 0;b < M;b ++) if (a != b) {
                ans += dp[i][a][b][0];
                if (i != v.size() - 1) ans += dp[i][a][b][1];
            }
        }
    }
    return ans;
};

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

int32_t main () {

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

    string 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 'll get(std::string)':
numbers.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 2;i < v.size();i ++) {
      |                    ~~^~~~~~~~~~
numbers.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 1;i < v.size();i ++) {
      |                    ~~^~~~~~~~~~
numbers.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 if (i != v.size() - 1) ans += dp[i][a][b][1];
      |                     ~~^~~~~~~~~~~~~~~
numbers.cpp: In function 'int check(std::string)':
numbers.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 1;i < v.size();i ++) if (v[i - 1] == v[i]) return 0;
      |                    ~~^~~~~~~~~~

Subtask #1
22.5 / 25.0

# 결과 실행 시간 메모리 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 512 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 Incorrect 1 ms 336 KB Output isn't 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 Incorrect 1 ms 336 KB Output isn't 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
68.3333333333 / 75.0

# 결과 실행 시간 메모리 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 Incorrect 1 ms 560 KB Output isn't 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 508 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 500 KB Output is correct
13 Correct 1 ms 504 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Incorrect 1 ms 336 KB Output isn't 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 2 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 2 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 336 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 504 KB Output is correct
36 Correct 1 ms 336 KB Output is correct
37 Correct 1 ms 336 KB Output is correct
38 Incorrect 1 ms 336 KB Output isn't correct
39 Incorrect 1 ms 572 KB Output isn't correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 384 KB Output is correct
42 Correct 1 ms 504 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