Submission

Score: 100

User: angpangSK

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.158 second

Submitted On: 2025-09-25 20:13:15

#include<bits/stdc++.h>

using namespace std;
using ll=long long int;
using pii=array<ll,2>;
vector<long long int> p;
ll dx[5]={0,1,8,6,9};
ll dy[5]={0,1,8,9,6};
const ll N=1e15;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll n,m;
    cin >> n >> m;
    queue<pii> q;
    q.push({0,100}); p.push_back(0);
    q.push({1,100}); p.push_back(1);
    q.push({8,100}); p.push_back(8);
    q.push({0,1000});
    q.push({11,1000}); p.push_back(11);
    q.push({88,1000}); p.push_back(88);
    q.push({69,1000}); p.push_back(69);
    q.push({96,1000}); p.push_back(96);
    while(!q.empty()){
        auto x=q.front()[0];
        auto y=q.front()[1];
        q.pop();
        if(x>N || y>N*100) continue;
        for(int i=0;i<5;i++){
            if(i!=0){
                p.push_back(x*10+dx[i]*y+dy[i]);
            }
            q.push({1ll*(x*10+dx[i]*y+dy[i]),y*100});
        }	
    }
    int ans=0;
    sort(p.begin(),p.end());
    auto v = lower_bound(p.begin(),p.end(),n)-p.begin();
    auto u = upper_bound(p.begin(),p.end(),m)-p.begin();
    cout << u-v;
}