Submission

Score: 100

User: letdown

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.034 second

Submitted On: 2025-10-12 19:18:40

#include <iostream>
#include <vector>

using namespace std;
vector<string> createStrobo(int cur, int len) {
    if (cur == 0) return {""};
    if (cur == 1) return {"0", "1", "8"};

    vector<string> strobo;
    vector<string> middle = createStrobo(cur-2, len);
    for (auto mid: middle) {
        if (cur > len) break;
        if (cur < len) strobo.push_back("0" + mid + "0");
        strobo.push_back("1" + mid + "1");
        strobo.push_back("6" + mid + "9");
        strobo.push_back("8" + mid + "8");
        strobo.push_back("9" + mid + "6");
    }
    return strobo;
}

int main() {
    long long low, high, ans=0;
    cin >> low >> high;

    int l = to_string(high).length();
    for (int i = 0; i <= l; i++) {
        vector<string> strobo = createStrobo(i, i);
        for (auto s : strobo) {
            if (s == "" || s[0] == '0') continue;
            long long sint = stoll(s);
            if (sint >= low && sint <= high) ans++;
        }
    }
    // vector<string> strobo = createStrobo(l, l);
    // for (auto s : strobo) {
    //     // cout << s << " ";
    //     if (s == "" || s[0] == '0') continue;
    //     long long sint = stoll(s);
    //     if (sint >= low && sint <= high) ans++;
    // }
    cout << ans;
    // vector<string> strobo = createStrobo(3, 3);
    // for (auto s : strobo) cout << s << " ";
}