Submission #1352190

#TimeUsernameProblemLanguageResultExecution timeMemory
1352190po_rag526Palindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms344 KiB
#include<bits/stdc++.h>
using namespace std;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define ll long long
#define int long long
#define all(x,off) x.begin()+off,x.end()
#define pb push_back 

const int N=5e5+10;
const ll inf=9e17;
const ll mod=1e9+7;

string num;
int dp[19][11][11][2][2][2];

int dfs(int pos,int prev1,int prev,int tight,int started,int state) {
  if (pos==(int)num.size()) {
    return state;
  }

  if (dp[pos][prev1][prev][tight][started][state]!=-1) {
    return dp[pos][prev1][prev][tight][started][state];
  }

  
  int ans=0;
  int lim=9;
  if (tight) lim=num[pos]-'0';
  for (int d=0;d<=lim;++d) {
    if (d>0||started) {
      int nw=state;
      if (d==prev1||d==prev) nw=1;
      ans+=dfs(pos+1,prev,d,tight&&(d==lim),1,nw);
    }
    else {
      ans+=dfs(pos+1,10,10,tight&&(d==lim),0,0);
    }
  }

  return dp[pos][prev1][prev][tight][started][state]=ans;
}

int solve(int y) {
  memset(dp,-1,sizeof(dp));
  num=to_string(y);

  if (y<=0) return 0;
  return dfs(0,10,10,1,0,0); 
}

void levi() {
  int l,r;
  cin>>l>>r;
  cout<<(r-l+1)-solve(r)+solve(l-1)<<'\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);int tt=1;//cin>>tt;
  while (tt--) levi();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...