Numerot

#include <bits/stdc++.h>
 
std::unordered_map<long, std::pair<long, long>> cache[10];
 
long pows[] = {
	1l,
	10l,
	100l,
	1000l,
	10000l,
	100000l,
	1000000l,
	10000000l,
	100000000l,
	1000000000l,
	10000000000l,
	100000000000l,
	1000000000000l,
	10000000000000l,
	100000000000000l,
	1000000000000000l,
	10000000000000000l,
	100000000000000000l,
	1000000000000000000l
};
 
std::pair<long, long> f(long luku, const long maxnum = 0) {
	long key = luku;
	if (cache[maxnum].find(key) != cache[maxnum].end()) {
		return cache[maxnum].find(key)->second;
	}
	if (luku < maxnum) {
		return {1, -maxnum};
	}
	if (luku <= 9) {
		if (maxnum == 0) {
			return {1, -luku};
		}
		return {2, -(luku + maxnum)};
	}
 
	long askelia = 0;
	long muutos = 0;
	while (luku > 9) {
		auto s = std::to_string(luku);
		bool muutettu = false;
		for (unsigned i = 1; i < s.length() - 1; ++i) {
			if (s[s.length() - 1 - i] != '0') {
				auto newmaxnum = maxnum;
				for (unsigned j = i + 1; j < s.length(); ++j) {
					int c = s[s.length() - 1 - j] - '0';
					if (c > newmaxnum) {
						newmaxnum = c;
					}
				}
				auto am = f(luku % pows[i+1], newmaxnum);
				askelia += am.first;
				muutos += am.second;
				luku += am.second;
				muutettu = true;
				break;
			}
		}
		if (!muutettu) {
			askelia += 1;
			auto num = std::max<long>({maxnum, s[0] - '0', *s.rbegin() - '0'});
			muutos -= num;
			luku -= num;
		}
	}
	cache[maxnum][key] = {askelia, muutos};
	return cache[maxnum][key];
}
 
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: TIME LIMIT EXCEEDED