제출 #1113920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113920		NoMercy	Palindrome-Free Numbers (BOI13_numbers)	C++17	90.83 / 100	2 ms	572 KiB

numbers

#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";
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 68.33333333333333 / 75