Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.5 kB
11
Indexable
Never
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> champNumbers;

void generateChampNumbers(long long num, int lastDigit) {
    if (num > 0 && num <= 1e18) {
        champNumbers.push_back(num);
    }
    
    if (lastDigit > 5 || num > 1e17) {
        return;
    }

    for (int i = 0; i <= 5; ++i) {
        if (i != lastDigit) {
            generateChampNumbers(num * 10 + i, i);
        }
    }
}

vector<long> ChampNumbers(const vector<vector<long>>& queries) {
    vector<long> results;
    for (const vector<long>& query : queries) {
        long long X = query[0];
        long long Y = query[1];

        int count = upper_bound(champNumbers.begin(), champNumbers.end(), Y) - 
                    lower_bound(champNumbers.begin(), champNumbers.end(), X);

        results.push_back(count);
    }
    return results;
}

int main() {
    generateChampNumbers(0, -1); // Start with 0, -1 as lastDigit since we haven't chosen any digit yet.
    sort(champNumbers.begin(), champNumbers.end());

    int Q;
    cin >> Q;

    vector<vector<long>> Q_X_Y(Q);
    for (int i = 0; i < Q; ++i) {
        long long X, Y;
        cin >> X >> Y;
        Q_X_Y[i].push_back(X);
        Q_X_Y[i].push_back(Y);
    }

    vector<long> result = ChampNumbers(Q_X_Y);

    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i != result.size() - 1) {
            cout << "\n";
        }
    }

    return 0;
}