Submission

PPPPPPPPPP

Score: 100

User: Ecir

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.070 second

Submitted On: 2025-01-14 17:22:27

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
#define twod array<ll,2>
vector<ll> ans;
const ll lim=1e15;
int fr[]={0,1,6,8,9};
int bk[]={0,1,9,8,6};
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  queue<twod> q;
  q.push({0,100}); ans.push_back(0);
  q.push({1,100}); ans.push_back(1);
  q.push({8,100}); ans.push_back(8);
  q.push({00,1000});
  q.push({11,1000}); ans.push_back(11);
  q.push({69,1000}); ans.push_back(69);
  q.push({88,1000}); ans.push_back(88);
  q.push({96,1000}); ans.push_back(96);
  while(!q.empty()){
    auto x=q.front();q.pop();
    if(x[1]>lim) continue;
    q.push({x[1]*fr[0]+x[0]*10+bk[0],x[1]*100});
    for(int i=1;i<=4;i++){
      q.push({x[1]*fr[i]+x[0]*10+bk[i],x[1]*100});
      ans.push_back(x[1]*fr[i]+x[0]*10+bk[i]);
    }
  }
  ll st,en;cin >> st >> en;
  ll sum=0;
  sort(ans.begin(),ans.end());
  for(auto e:ans){
    if(e>en) break;
    if(e>=st) sum++;
  }     
  cout << sum;
                                
  return 0;
}