Submission

Score: 100

User: loop

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.012 second

Submitted On: 2026-10-10 18:33:37

#include <cstdio>

long long lo, hi, cnt = 0;
const char A[5] = {'0', '1', '6', '8', '9'}, B[5] = {'0', '1', '9', '8', '6'};
char d[20];

// Fill digits from both ends towards the middle; 0, 1, 8 may sit in the middle of an odd length.
void build(int L, int i) {
    int j = L - 1 - i;
    if (i > j) {
        long long x = 0;
        for (int k = 0; k < L; k++) x = x * 10 + (d[k] - '0');
        if (x >= lo && x <= hi) cnt++;
        return;
    }
    for (int k = 0; k < 5; k++) {
        if (i == 0 && L > 1 && A[k] == '0') continue;
        if (i == j && (A[k] == '6' || A[k] == '9')) continue;
        d[i] = A[k];
        d[j] = B[k];
        build(L, i + 1);
    }
}

int main() {
    scanf("%lld %lld", &lo, &hi);
    for (int L = 1; L <= 16; L++) build(L, 0);
    printf("%lld\n", cnt);
    return 0;
}