Untitled

 avatar
unknown
plain_text
a month ago
1.5 kB
1
Indexable
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define __ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pii pair<ll,ll>

map<pii,ll> memoize;

ll binom(ll n, ll k) {
    if (k > n) return 0;
    
    if (memoize[make_pair(n,k)] == 0) {
        ll res = 1;
        k = min(k, n - k);
        for (ll i = 1; i <= k; i++) {
            res = res * (n - i + 1) / i;
        }
        memoize[make_pair(n,k)] = res;
    }
    
    return memoize[make_pair(n,k)];
}

ll T(ll k) {
    return binom(k + 10, 10) - k - 1;
}

string build_number(ll m, ll min_d, ll max_d, ll M) {
    if (m == 0) return "";
    ll cum = 0;
    for (ll d = min_d; d <= max_d; d++) {
        ll count = (m == 1) ? 1 : binom(m - 1 + d, m - 1);
        if (cum + count >= M) {
            string result = to_string(d);
            if (m > 1) {
                ll sub_M = M - cum;
                result += build_number(m - 1, 0, d, sub_M);
            }
            return result;
        }
        cum += count;
    }
    return ""; // if it got here sumn went wrong
}

string solve(ll N) {
    ll k = 1;
    while (T(k) < N) k++;
    ll N_prime = (k == 1) ? N : N - T(k - 1);
    return build_number(k, 1, 9, N_prime);
}

int main() {__
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        ll N;
        cin >> N;
        cout << solve(N) << endl;
    }
    return 0;
}
Editor is loading...
Leave a Comment