Submission #482977

#	Time	Username	Problem	Language	Result	Execution time	Memory
482977		lto5	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	1 ms	460 KiB

numbers

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

const int MAX_N = 20;
const int MAX_D = 15;

int num[MAX_N];
long long f[MAX_N][2][2][MAX_D][MAX_D];

//position i, <=, trailing zero, num[i - 2], num[i - 1]
long long dp(int i, bool limit, bool f0, int prev1, int prev2){
  if(i < 0)
    return 1;

  if(f[i][limit][f0][prev1][prev2] != -1)
    return f[i][limit][f0][prev1][prev2];

  int max_d = (limit ? num[i] : 9);
  long long res = 0;

  for(int c = 0; c <= max_d; c++){
    if(c == prev1 || c == prev2)
      continue;

    bool new_limit = limit && c == max_d;
    bool new_f0 = f0 && i >= 1 && c == 0;
    int new_prev1, new_prev2;

    if(new_f0 == true)
      new_prev1 = 10, new_prev2 = 10;
    else
      new_prev1 = prev2, new_prev2 = c;

    res += dp(i - 1, new_limit, new_f0, new_prev1, new_prev2);
  }

  return f[i][limit][f0][prev1][prev2] = res;
}

long long solve(long long x){
  int n = 0;
  do{
    num[n++] = x % 10;
    x /= 10;
  } while(x > 0);

  memset(f, -1, sizeof(f));
  return dp(n - 1, true, true, 10, 10);
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  long long a, b;
  cin >> a >> b;

  cout << solve(b) - solve(a - 1);

  return 0;
}
    

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75