Submission #504101

#	Time	Username	Problem	Language	Result	Execution time	Memory
504101		vlad_TT	Palindrome-Free Numbers (BOI13_numbers)	C++17	90 / 100	1 ms	332 KiB

numbers

#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 && d2 != 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' && i >= 0) {
    a[i] = '9';
    i--;
  }
  a[i]--;
  if (a[0] == '0' && a.size() > 1) {
    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 (stderr)

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