We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Decibinary Numbers
  5. Discussions

Decibinary Numbers

  • dehaka
     + 0 comments

    hard question, finally got it working after numerous modifications to improve time. hint: dont use pow(2, K), it's slow as fk, precompute the powers of 2 and 10

    calculating global information requires O(300000 * 19 * 10). let A be the x'th decibinary number. each query for x <= 10^16 takes O(log_2(300000) + log_10(A))

    pass all tests no timeout

    vector<vector<long>> cache(300000, vector<long>(19)), two(10, vector<long>(19)), ten(10, vector<long>(19));
vector<long> decimalValue;

void global_information() {
    for (int K = 0; K <= 18; ++K) {
        for (int d = 0; d <= 9; ++d) {
            two[d][K] = d * pow(2, K);
            ten[d][K] = d * pow(10, K);
        }
    }
    for (int K = 0; K <= 18; ++K) cache[0][K] = 1;
    for (int n = 0; n <= 9; ++n) cache[n][0] = 1;
    for (int n = 1; n < cache.size(); ++n) {
        for (int K = 1; K <= 18; ++K) {
            for (int d = 0; d <= 9 and n - two[d][K] >= 0; ++d) cache[n][K] = cache[n][K] + cache[n - two[d][K]][K - 1];
        }
    }
    decimalValue.push_back(1);
    for (int n = 1; n < cache.size(); ++n) decimalValue.push_back(decimalValue.back() + cache[n][18]);
}

long decibinaryNumbers(long x) {
    if (x == 1) return 0;
    long answer = 0;
    int v = distance(decimalValue.begin(), lower_bound(decimalValue.begin(), decimalValue.end(), x));
    long position = x - decimalValue[v - 1];
    while (v > 0) {
        int K = distance(cache[v].begin(), lower_bound(cache[v].begin(), cache[v].end(), position)), d = 0;
        if (K == 0) {
            answer = answer + v;
            break;
        }
        long temp = 0;
        for (int digit = 0; digit <= 9 and v - two[digit][K] >= 0; ++digit) {
            temp = temp + cache[v - two[digit][K]][K - 1];
            if (position <= temp) {
                d = digit;
                break;
            }
        }
        answer = answer + ten[d][K];
        position = position - temp + cache[v - two[d][K]][K - 1];
        v = v - two[d][K];
    }
    return answer;
}

int main()
{
    global_information();
    int q;
    long x;
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> x;
        cout << decibinaryNumbers(x) << '\n';
    }
}