Numerot

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const ull INF = 9 * (ull)1e18;
const int K = 20;
const int D = 10;
pair<ull, int> dp[K + 1][D][D];

pair<ull, int> advance(pair<ull, int> cur, int k, int b, int d) {
	// if (k <= 3) cerr << "advance(" << cur.first << "," << cur.second << " ;; " << k << ' ' << b << ' ' << d << "): ";
	for (; d >= 0; --d) {
		auto tmp = dp[k-1][max(b, d)][cur.second];
		cur.first += tmp.first;
		cur.second = tmp.second;
	}
	// if (k <= 3) cerr << cur.first << ' ' << cur.second << '\n';
	return cur;
}

ull count(ull v) {
	if (v < 10) return 1;

	// cerr << "count " << v << ": ";

	vector<int> nums;
	while(v > 0) {
		nums.push_back(v % 10);
		v /= 10;
	}
	int k = nums.size();

	vector<int> prefs(k, 0);
	for (int i = k-2; i >= 0; --i) prefs[i] = max(prefs[i+1], nums[i+1]);

	pair<ull, int> res = dp[0][prefs[0]][nums[0]];
	for (int j = 1; j < k; ++j) {
		if (nums[j] == 0) continue;
		res = advance(res, j, prefs[j], nums[j] - 1);
	}
	// cerr << res.first << endl;
	return res.first;
}

void solve() {
	ull x;
	cin >> x;

	ull low = 1;
	ull high = INF;
	while(low != high) {
		ull mid = (low + high) >> 1;
		if (count(mid) >= x) high = mid;
		else low = mid + 1;
		// cerr << "range: " << low << ' ' << high << endl;
	}
	cout << low << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	for (int b = 0; b < 10; ++b) {
		for (int r = 0; r < 10; ++r) {
			if (b <= r) {
				dp[0][b][r] = (b == 0 ? make_pair<ull, int>((r != 0), 0) : make_pair<ull, int>(2, 10 - b));
			} else {
				dp[0][b][r] = {1, 10 - max(0, b - r)};
			}
		}
	}

	for (int k = 1; k <= K; ++k) {
		for (int b = 0; b < 10; ++b) {
			for (int r = 0; r < 10; ++r) {
				dp[k][b][r] = advance({0, r}, k, b, 9);
			}
		}
	}
	
	int t;
	cin >> t;
	for (int ti = 0; ti < t; ++ti) solve();
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED