Submission

Score: 50

User: mocngaijakraila

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.015 second

Submitted On: 2026-06-21 16:53:45

// #include<bits/stdc++.h>
// using namespace std;
// #define ll long long

// bool f(ll i, ll j, string t) {
//     while(i <= j) {
//         if((t[i] == '1' && t[j] ==  '1') || (t[i] == '0' && t[j] == '0') || (t[i] == '8' && t[j] == '8') || (t[i] == '6' && t[j] == '9') || (t[i] == '9' && t[j] == '6')) {

//             i++;
//             j--;
//         }
//         else {
//             return false;
//         }
//     }

//     return true;
// }

// int main() {
//     cin.tie(0)->sync_with_stdio(0);

//     ll l, u;
//     cin >> l >> u;

//     ll cnt = 0;

//     while(l <= u) {

//         auto t = to_string(l);


//         int i = 0, j = t.length()-1;

//         if(f(i, j, t)) cnt++;

//         l++;



//     }
//     cout << cnt;


//     return 0;
// }


#include<bits/stdc++.h>
using namespace std;
using ll = long long;

vector<string> strobo;
ll strob;
ll l, u;
ll ans = 0;
bool bound = false; 
// string t1="", t2="";

void basecase(int n) {
    if(n == 1 || n ==  0 || n == 8) ans++;
}

void rec(int n,  string t1, string t2, int i) {
    if(n == i)  {
        reverse(t2.begin(), t2.end());

        strob = stoll(t1 + t2);
        if(strob >= l && strob <= u) ans++;

        strob = stoll(t1 + "1" + t2);
        if(strob >= l && strob <= u) ans++;

        strob = stoll(t1 + "0" + t2);
        if(strob >= l && strob <= u) ans++;

        strob = stoll(t1 + "8" + t2);
        if(strob >= l && strob <= u) ans++;
        
        // cout << t1+t2 << '\n';
        // cout << t1 << '1' << t2 << '\n';
        // cout << t1 << '0'<< t2 << '\n';
        // cout << t1 << '8'<< t2 << '\n';

        reverse(t2.begin(), t2.end());
        
        return;
    }

    
    rec(n + 1, t1 += '1', t2 += '1', i);
    t1.pop_back();
    t2.pop_back();

    if(!t1.empty() && !t2.empty()) {
        rec(n + 1, t1 += '0', t2 += '0', i);
        t1.pop_back();
        t2.pop_back();
    }
    
    rec(n + 1, t1 += '8', t2 += '8', i);
    t1.pop_back();
    t2.pop_back();

    rec(n + 1, t1 += '6', t2 += '9', i);
    t1.pop_back();
    t2.pop_back();

    rec(n + 1, t1 += '9', t2 += '6', i);
    t1.pop_back();
    t2.pop_back();
    
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> l >> u;
    
    ll tm1 = l, tm2 = u;
    int cnt1 = 0, cnt2 = 0;


    while(tm1 > 0) {
        tm1/=10;
        cnt1++;
    }

    while(tm2>0) {
        tm2/=10;
        cnt2++;
    }


    if(cnt1 % 2 == 0 && cnt1 > 0) cnt1--;
    if(cnt2 % 2 == 0 && cnt2 > 0) cnt2--;
    

    cnt1/=2;
    cnt2/=2;

    if(cnt1 <= 1)  {
        // cout << "DO";
        for(int i = l; i <= 9 && i <= u; i++) {
            basecase(i);
        }
        
    }
    

    rec(0, "", "", cnt2);

    cout << ans;


    return 0;
}