Submission #790558

#	Time	Username	Problem	Language	Result	Execution time	Memory
790558		tch1cherin	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	340 KiB

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