Untitled
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