Submission

PPPPPPPPPP

Score: 100

User: hmmm

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.197 second

Submitted On: 2025-01-26 15:29:31

#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;
//unordered_set<string> t;

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();
//		cout << x << ' ' << y << "\n";
		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]);
			}
//			cout << x*10+dx[i]*y+dy[i] << "\n";
			q.push({1ll*(x*10+dx[i]*y+dy[i]),y*100});
		}	
	}
	int ans=0;
	sort(p.begin(),p.end());
//	for(auto e:p){
//		cout << e << "\n";
//	}
	auto v=lower_bound(p.begin(),p.end(),n)-p.begin();
	auto u=upper_bound(p.begin(),p.end(),m)-p.begin();
//	cout << p.size();
	cout << u-v;
}