Submission

PPxxxxxxxx

Score: 20

User: Ecir

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.172 second

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

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
const ll lim=1000000000;
map<ll,int> mp;
char fr[5]={'0','1','6','8','9'};
char bk[5]={'0','1','9','8','6'};
int tran(string s){
	ll ans=0;
	int cnt=0;
//	cout << s << " ";
	while(s!=""){
		ans+=(s[s.size()-1]-'0')*pow(10,cnt);
		cnt++;
		s.pop_back();
	}
	while(ans%10==0 && ans!=0) ans=ans/10;
//	cout << ans << "\n";
	return ans;
}
int main(){
	ios::sync_with_stdio(0);cin.tie();
	ll s,e;
	cin  >> s >> e;
	queue<string> q;
	q.push("0");
	q.push("1");
	q.push("8");
	q.push("00");
	q.push("69");
	q.push("96");
	q.push("11");
	q.push("88");
	while(!q.empty()){
		string x=q.front();q.pop();
		ll y=tran(x);
//		cout << x << "\n";
		if(x[0]!=0 && x[x.size()-1]==0){
			y/=10;
			mp[y]=1;
//			cout << y << "\n";
		}
		else{
			mp[y]=1;
//			cout << y << "\n";
		}
		for(int i=0;i<=4;i++){
			string w="";
			w+=fr[i];
			w+=x;
			w+=bk[i];
			if(w.size()>10) break;
			q.push(w);
		}
	}
	int ans=0;
	for(int i=s;i<=e;i++){
		ans+=mp[i];
	}
	cout << ans;
	
	return 0;
}