Numerot

#include <bits/stdc++.h>
 
std::pair<long, long> cache[10 * 10 * 10 * 20];
std::pair<long, long> helppo(int alkumax, int ylin, int nollia, int alin) {
	int key = alkumax + 10 * (ylin + 10 * (alin + 10 * nollia));
	auto val = cache[key];
	if (val.first != 0) {
		return val;
	}
 
	long askelia = 0, muutos = 0;
	while (ylin > 0) {
		// Nyt luku on muotoa {ylin}00000{alin}
		// Aiheutetaan kymmenylitys, jossa ylin laskee yhdellä.
		int maxnum = std::max({alkumax, ylin, alin});
		if (maxnum <= alin) {
			int maxnum2 = std::max({alkumax, ylin, alin - maxnum});
			askelia += 2;
			muutos -= maxnum + maxnum2;
			alin = (100 + alin - maxnum - maxnum2) % 10;
		} else {
			askelia += 1;
			muutos -= maxnum;
			alin = (100 + alin - maxnum) % 10;
		}
		ylin -= 1;
 
		if (nollia > 0) {
			// Nyt luku on muotoa {ylin}99999{alin}
			// Tuhotaan yhdeksiköt pienimmästä alkaen.
			for (int i = 0; i < nollia - 1; ++i) {
				auto am = helppo(9, 9, i, alin);
				askelia += am.first;
				muutos += am.second;
				alin = (9099999999999999990l + alin + am.second) % 10;
			}
 
			// Nyt luku on muotoa {ylin}90000{alin}
			int i = nollia - 1;
			int maxnum = std::max(alkumax, ylin);
			auto am = helppo(maxnum, 9, i, alin);
			askelia += am.first;
			muutos += am.second;
			alin = (9099999999999999990l + alin + am.second) % 10;
		}
	}
 
	return cache[key] = {askelia, muutos};
}
 
std::pair<long, long> f(long luku, int maxnum = 0) {
	long askelia = 0, muutos = 0;
	long kymppi = 10;
	int nollia = 0;
	while (luku > 9) {
		int ylin = luku / kymppi % 10;
		int alin = luku % 10;
		auto s = std::to_string(luku / kymppi / 10);
		int alkumax = *std::max_element(s.begin(), s.end()) - '0';
		auto am = helppo(std::max(maxnum, alkumax), ylin, nollia, alin);
		askelia += am.first;
		muutos += am.second;
		luku += am.second;
		kymppi *= 10;
		nollia += 1;
	}
	return {askelia, muutos};
}
 
long g(long x) {
	return f(x).first + 1;
}
 
int main() {
	int t;
	std::cin >> t;
	for (int i = 0; i < t; ++i) {
		long x;
		std::cin >> x;
		if (x == 1) {
			std::cout << "1\n";
			continue;
		}
		long k0 = 9, k1 = 9000000000000000001l;
		while (k1 - k0 > 1) {
			long k = ((unsigned long)k1 + (unsigned long)k0) / 2;
			if (g(k) < x) {
				k0 = k;
			} else {
				k1 = k;
			}
		}
		std::cout << k1 << "\n";
	}
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED