Submission

PPPPPPPPPP

Score: 100

User: admin

Problemset: Strobogrammatic Numbers

Language: cpp

Time: 0.043 second

Submitted On: 2024-11-25 14:42:01

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// ฟังก์ชันตรวจสอบว่าเลขที่กำหนดสามารถเป็น Strobogrammatic number ได้หรือไม่
bool isStrobogrammatic(const string& num) {
    int left = 0;
    int right = num.size() - 1;
    while (left <= right) {
        if ((num[left] == '0' && num[right] == '0') ||
            (num[left] == '1' && num[right] == '1') ||
            (num[left] == '6' && num[right] == '9') ||
            (num[left] == '8' && num[right] == '8') ||
            (num[left] == '9' && num[right] == '6')) {
            left++;
            right--;
        } else {
            return false;
        }
    }
    return true;
}

// ฟังก์ชันสร้าง Strobogrammatic numbers จากขนาดที่กำหนด
vector<string> generateStrobogrammatic(int n, int totalLength) {
    if (n == 0) return {""};
    if (n == 1) return {"0", "1", "8"};

    vector<string> middles = generateStrobogrammatic(n - 2, totalLength);
    vector<string> result;
    for (const string& middle : middles) {
        if (n != totalLength) result.push_back("0" + middle + "0");
        result.push_back("1" + middle + "1");
        result.push_back("6" + middle + "9");
        result.push_back("8" + middle + "8");
        result.push_back("9" + middle + "6");
    }
    return result;
}

// ฟังก์ชันนับจำนวน Strobogrammatic numbers ในช่วงที่กำหนด
int strobogrammaticInRange(const string& low, const string& high) {
    int count = 0;
    
    for (int len = low.size(); len <= high.size(); ++len) {
        vector<string> strobogrammaticNums = generateStrobogrammatic(len, len);
        
        for (const string& num : strobogrammaticNums) {
            if ((num.size() == low.size() && num < low) || (num.size() == high.size() && num > high)) {
                continue;
            }
            if (num[0] != '0' || num.size() == 1) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    string low, high;
    //cout << "กรุณาใส่ค่า low: ";
    cin >> low;
    //cout << "กรุณาใส่ค่า high: ";
    cin >> high;
    
    int result = strobogrammaticInRange(low, high);
    cout << result << endl;
    
    return 0;
}