답안 #790558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790558	2023-07-22T20:44:24 Z	tch1cherin	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	340 KB

numbers

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 26;
int64_t DP[MAX_N][11][11];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int64_t l, r;
  cin >> l >> r;
  r++;
  string _L = to_string(l), _R = to_string(r);
  reverse(_L.begin(), _L.end());
  reverse(_R.begin(), _R.end());
  while (_L.size() < MAX_N - 1) {
    _L += '0' + 10;
  }
  while (_R.size() < MAX_N - 1) {
    _R += '0' + 10;
  }
  reverse(_L.begin(), _L.end());
  reverse(_R.begin(), _R.end());
  auto Count = [](string R) {
    memset(DP, 0, sizeof DP);
    bool good = true;
    for (int i = 2; i < MAX_N - 1; i++) {
      if ((R[i - 1] != '0' + 10) && (R[i - 1] == R[i - 2] || (i >= 3 && R[i - 1] == R[i - 3]))) {
        good = false;
      }
      for (int A = 0; A <= 10; A++) {
        for (int B = 0; B <= 10; B++) {
          for (int C = 0; C < 10; C++) {
            if (A == C || B == C) {
              continue;
            }
            if (R[i] != '0' + 10 && C < R[i] - '0' && A == R[i - 2] - '0' && B == R[i - 1] - '0' && good) {
              DP[i + 1][B][A == 10 && B == 10 && C == 0 ? 10 : C]++;
            }
            DP[i + 1][B][A == 10 && B == 10 && C == 0 ? 10 : C] += DP[i][A][B]; 
          }
        }
      }
    }
    int64_t ans = 0;
    for (int A = 0; A <= 10; A++) {
      for (int B = 0; B <= 10; B++) {
        ans += DP[MAX_N - 1][A][B];
      }
    }
    return ans;
  };
  cout << Count(_R) - Count(_L) << "\n";
}

Subtask #1

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	340 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

Subtask #2

75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	0 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct
40	Correct	1 ms	340 KB	Output is correct
41	Correct	1 ms	340 KB	Output is correct
42	Correct	1 ms	212 KB	Output is correct
43	Correct	1 ms	340 KB	Output is correct
44	Correct	1 ms	340 KB	Output is correct
45	Correct	1 ms	212 KB	Output is correct