Submission

xxxxxxxxxx

Score: 0

User: hmmm

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.217 second

Submitted On: 2025-01-26 13:57:34

#include<bits/stdc++.h>
using namespace std;
vector<long long int> p;
unordered_set<string> t;
string str;

inline long long int chk(string s){
	long long int ans=0,n=s.size();
	for(int i=0;i<n;i++){
		ans=ans*10+s[i]-'0';
	}
	return ans;
}

inline void rec(string s){
	if(s[0]!='0'){
		t.insert(s);
	}
	if(s.size()>14) return;
	str='0'+s+'0';
	rec(str);
	str='1'+s+'1';
	rec(str);
	str='8'+s+'8';
	rec(str);
	str='6'+s+'9';
	rec(str);
	str='9'+s+'6';
	rec(str);

}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m;
	cin >> n >> m;
	queue<string> q;
	q.push("");
	q.push("1");
	q.push("0");
	q.push("8");
	while(!q.empty()){
		string s=q.front();
		q.pop();
		if(s[0]!='0'){
			t.insert(s);
		}
		if(s.size()>15) continue;
		str='0'+s+'0';
		q.push(str);
		str='1'+s+'1';
		q.push(str);
		str='8'+s+'8';
		q.push(str);
		str='6'+s+'9';
		q.push(str);
		str='9'+s+'6';
		q.push(str);	
			
	}
	int ans=0;
	
	for(auto e:t){
		p.push_back(chk(e));
//		if(n<=e && e<=m) ans++;
	}
	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;
}