제출 #1294742

#제출 시각아이디문제언어결과실행 시간메모리
1294742JohanPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms580 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int dp[20][11][11][2];
int f(int pos, int last1, int last2, bool ok){
  if(pos == s.size())
    return 1;
  if(dp[pos][last1][last2][ok] != -1)
    return dp[pos][last1][last2][ok];
  int limit = (ok == true ? s[pos] - '0' : 9);
  int ans = 0;
  for(int i = 0; i <= limit; i++){
    if(last1 == 10 && last2 == 10 && i == 0){
      if(ok == true && limit == i)
        ans += f(pos + 1, last1, last2, 1);
      else 
        ans += f(pos + 1, last1, last2, 0);
    }
    else {
      if(i == last1 || i == last2)
        continue;
      if(ok == true && limit == i)
        ans += f(pos + 1, i, last1, 1);
      else 
        ans += f(pos + 1, i, last1, 0);
    }
  }
  return dp[pos][last1][last2][ok] = ans;
}
int solve(int x){
  if(x == -1)return 0;
  s = to_string(x);
  memset(dp, -1, sizeof(dp));
  return f(0, 10, 10, 1);
}
signed main(){
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  cin.tie(nullptr)->sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  cout << solve(b) - solve(a - 1) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...