Submission

Score: 60

User: lazy

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.021 second

Submitted On: 2025-10-14 23:41:40

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

vector<vector<string>> dp(25);
map<char, char> pairs = {
    {'0','0'},
    {'1','1'},
    {'6','9'},
    {'8','8'},
    {'9','6'}
};

vector<string> at_i_digit(int i, int outer_len) {
    if (i == 0) return {""};
    if (i == 1) return {"0","1","8"};
    if (!dp[i].empty()) return dp[i];

    vector<string> smaller = at_i_digit(i - 2, outer_len);
    vector<string> result;

    for (auto &s : smaller) {
        for (auto &[a, b] : pairs) {
            if (a == '0' && i == outer_len) continue;
            result.push_back(string(1, a) + s + string(1, b));
        }
    }

    dp[i] = result;
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long lower, upper;
    cin >> lower >> upper;

    int digits_low = to_string(lower).length();
    int digits_high = to_string(upper).length();

    long long count = 0;

    for (int len = digits_low; len <= digits_high; len++) {
        vector<string> strobo = at_i_digit(len, len);
        for (auto &s : strobo) {
            long long num = stoll(s);
            if (num >= lower && num <= upper) count++;
        }
    }

    cout << count;
    return 0;
}