Submission #1300476

#TimeUsernameProblemLanguageResultExecution timeMemory
1300476ayazPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
2 ms644 KiB
#include <array>
#include <cassert>
#include <cstddef>
#include <cstring>
#include <functional>
#include <iostream>
#include <algorithm>
#include <chrono>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define int ll

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int sz = 1200, inf = 1000000000;
const ll mod = 1000000007, INF = 1000000000000000000;

const int D = 11;
const int N = 20;

int dp[N][D][D][2];
string s;
int solve(int pos, int d1, int d2, int block) {
  if (pos == isz(s)) return 1;
  if (dp[pos][d1][d2][block] != -1) return dp[pos][d1][d2][block];
  int res = 0;
  if (!d2) res += solve(pos + 1, d1, d2, 0);
  int st = 1 + (d2 == 0 ? 1 : 0);
  if (!block) {
    for (int d3 = st; d3 < D; d3++) {
      if (d3 != d1 && d3 != d2) {
        res += solve(pos + 1, d2, d3, 0);
      }
    }
  } else {
    int e = s[pos] - '0' + 1;
    for (int d3 = st; d3 <= e; d3++) {
      if (d3 != d1 && d3 != d2) {
        if (d3 == e) {
          res += solve(pos + 1, d2, d3, 1);
        } else {
          res += solve(pos + 1, d2, d3, 0);
        }
      }
    }
  }
  return dp[pos][d1][d2][block] = res;
}
int solve(int x) {
  if (x == -1) return 0;
  memset(dp, -1, sizeof(dp));
  s = to_string(x);
  return solve(0, 0, 0, 1);
}
void precompute() {}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  freopen("err.log", "w", stderr);
  freopen("in.txt", "r", stdin);
#endif
  precompute();

  int a, b;
  cin >> a >> b;
  cout << solve(b) - solve(a - 1) << '\n';
  return 0;    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...