Submission

Score: 10

User: angpangSK

Problemset: Strobogrammatic Numbers

Language: c

Time: 0.006 second

Submitted On: 2025-09-25 20:06:11

#include <stdio.h>
#include <string.h>

#define MAXLEN 20

const char *lowS, *highS;
long long ans = 0;

const char pairsL[] = {'0','1','6','8','9'};
const char pairsR[] = {'0','1','9','8','6'};

void buildAndCount(char *buf, int l, int r) {
    if (l > r) {
        buf[r+1] = '\0';
        int len = strlen(buf);
        if (len > 1 && buf[0] == '0') return;
        int lowLen = strlen(lowS);
        int highLen = strlen(highS);
        if (len < lowLen || len > highLen) return;
        if (len == lowLen && strcmp(buf, lowS) < 0) return;
        if (len == highLen && strcmp(buf, highS) > 0) return;
        ans++;
        return;
    }
    if (l == r) {
        const char mid[] = {'0','1','8'};
        for (int i = 0; i < 3; i++) {
            buf[l] = mid[i];
            buildAndCount(buf, l+1, r-1);
        }
        return;
    }
    for (int i = 0; i < 5; i++) {
        if (l == 0 && pairsL[i] == '0' && (r > 0)) continue;
        buf[l] = pairsL[i];
        buf[r] = pairsR[i];
        buildAndCount(buf, l+1, r-1);
    }
}

int main() {
    static char lowBuf[MAXLEN], highBuf[MAXLEN], buf[MAXLEN];
    if (scanf("%s", lowBuf) != 1) return 0;
    if (scanf("%s", highBuf) != 1) return 0;
    lowS = lowBuf;
    highS = highBuf;
    int minLen = strlen(lowS);
    int maxLen = strlen(highS);
    for (int len = minLen; len <= maxLen; len++) {
        buf[len] = '\0';
        buildAndCount(buf, 0, len - 1);
    }
    printf("%lld\n", ans);
    return 0;
}