oj.uz

Submission #504081

# Submission time Handle Problem Language Result Execution time Memory
504081 2022-01-09T17:08:21 Z vlad_TT Palindrome-Free Numbers (BOI13_numbers) C++17
90 / 100
 1 ms 388 KB 
#include <iostream>
#include <string.h>

const int MAX_N = 19;
const int MAX_D = 9;
const int LT = 0;
const int EQ = 1;
const int GT = 2;
long long dp[1 + MAX_N][3][1 + MAX_D][1 + MAX_D];

long long count(std::string s) {
  int n = s.size();
  memset(dp, 0, sizeof(dp));
  for (int i = 10; i <= 99; i++) {
    if (i % 10 != i / 10) {
      int nr = (s[0] - '0') * 10 + s[1] - '0';
      if (i < nr) {
        dp[2][LT][i / 10][i % 10]++;
      } else if (i == nr) {
        dp[2][EQ][i / 10][i % 10]++;
      } else {
        dp[2][GT][i / 10][i % 10]++;
      }
    }
  }
  for (int i = 3; i <= n; i++) {
    for (int d1 = 0; d1 <= 9; d1++) {
      for (int d2 = 0; d2 <= 9; d2++) {
        if (d1 != d2) {
          for (int d3 = 0; d3 <= 9; d3++) {
            if (d1 != d3) {
              int cif = s[i - 1] - '0';
              if (d1 < cif) {
                dp[i][LT][d2][d1] += dp[i - 1][LT][d3][d2] + dp[i - 1][EQ][d3][d2];
                dp[i][GT][d2][d1] += dp[i - 1][GT][d3][d2];
              } else if (d1 == cif) {
                dp[i][LT][d2][d1] += dp[i - 1][LT][d3][d2];
                dp[i][EQ][d2][d1] += dp[i - 1][EQ][d3][d2];
                dp[i][GT][d2][d1] += dp[i - 1][GT][d3][d2];
              } else {
                dp[i][LT][d2][d1] += dp[i - 1][LT][d3][d2];
                dp[i][GT][d2][d1] += dp[i - 1][EQ][d3][d2] + dp[i - 1][GT][d3][d2];
              }
            }
          }
        }
      }
    }
  }
  long long answer = 10;
  for (int i = 0; i <= 99; i++) {
    answer += dp[n][LT][i / 10][i % 10] + dp[n][EQ][i / 10][i % 10];
  }
  for (int i = 1; i < n; i++) {
    for (int j = 0; j <= 99; j++) {
      answer += dp[i][LT][j / 10][j % 10] + dp[i][EQ][j / 10][j % 10] + dp[i][GT][j / 10][j % 10];
    }
  }
  return answer;
}

int main() {
  std::string a, b;
  std::cin >> a >> b;
  if (a == "0") {
    std::cout << count(b);
    return 0;
  }
  int i = a.size() - 1;
  while (a[i] == 0) {
    a[i] = '9';
    i--;
  }
  a[i]--;
  if (a[0] == '0') {
    std::string tmp = "";
    for (int i = 1; i < a.size(); i++) {
      tmp += a[i];
    }
    a = tmp;
  }
  std::cout << count(b) - count(a);
  return 0;
}

Compilation message

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

Subtask #1
15.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB Output isn't correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 0 ms 332 KB Output isn't correct
6 Incorrect 1 ms 388 KB Output isn't correct
7 Incorrect 0 ms 332 KB Output isn't correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Correct 0 ms 324 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Incorrect 1 ms 296 KB Output isn't correct
16 Correct 1 ms 288 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Incorrect 0 ms 332 KB Output isn't correct
19 Correct 1 ms 280 KB Output is correct
20 Correct 0 ms 332 KB Output is correct

Subtask #2
75.0 / 75.0

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