Numerot

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 100;
const int M = 1e5;

const ll INF = 1e18;


ll a[10][N]; //Answer for small values
ll b[10][N]; //Where one ends up after reducing the small value
ll A[10][10][100]; //Answer for values near powers of ten
ll B[10][10][100]; //Where one ends up after reducing the value near power of ten


ll getFirstDigit(ll x) {
	int k = 0;
	ll po = 1;
	while(po*10 <= x) {
		po *= 10;
		++k;
		if(k == 18) break;
	}
	ll d = 1;
	while(d < 9 && (d+1)*po <= x) {
		++d;
	}
	return d;	
}

ll deleteFirstDigit(ll x) {
	ll po = 1;
	int k = 0;
	while(po*10 <= x) {
		++k;
		po *= 10;
		if(k == 18) break;
	}
	ll d = 1;
	while(d < 9 && (d+1)*po <= x) ++d;
	return x - po*d;
}

inline ll getK(ll x) {
	ll k = 1;
	ll po = 1;
	while(po*10 <= x) {
		po *= 10;
		++k;
		if(k == 19) {
			return k;
		}
	}
	return k;
}


ll getEn(ll d, ll x) {
	if(x < N) return b[d][x];
	ll D = getFirstDigit(x);
	ll e = getEn(max(d, D), deleteFirstDigit(x));
	if(e == 0) {
		e = -max(d, D);
	}
	e += 10; e %= 10;
	for(ll i = D-1; i >= 1; --i) {
		e = B[max(d, i)][e][getK(x)-1];
		if(e == 0) {
			e -= max(d, i);
		}
		e += 10;
		e %= 10;
	}
	return B[d][e][getK(x)-1];
}


ll calc(ll d, ll x) {
	if(x < N) {
		return a[d][x];
	}
	ll D = getFirstDigit(x);
	ll ans = calc(max(d, D), deleteFirstDigit(x));
	ll e = getEn(max(d, D), deleteFirstDigit(x));
	if(e == 0) {
		++ans;
		e -= max(d, D);
	}
	e+=10; e%=10;

	ll k = getK(x);
	for(ll i = D-1; i >= 1; --i) {	
		ans += A[max(d, i)][e][k-1];
		e = B[max(d, i)][e][k-1];
		if(e == 0) {
			++ans;
			e -= max(d, i);
		}
		e+=10; e%=10;
	}
	ans += A[d][e][k-1];
	return ans;
}



ll g(ll i) {
	ll ans = 1;
	while(i > 0) {
		ans = max(ans, i%10);
		i/=10;
	}
	return ans;
}



ll f[M];

int main() {
	ofstream out;
	out.open("output3.txt");

	for(ll x = 1; x < N; ++x) {
		for(ll d = 0; d < 10; ++d) {
			ll j = max(d, g(x));
			ll y = x - j;
			if(y < 0) {
				a[d][x] = 1;
				b[d][x] = y;
				continue;
			}
			a[d][x] = a[d][y] + 1;
			b[d][x] = b[d][y];
		}
	}

	ll po = 1;
	for(int k = 1; k <= 18; ++k) {
		po *= 10;
		for(int d = 0; d < 10; ++d) {
			for(int x = 1; x <= 9; ++x) {
				//Consider the number 10^k - (10 - x)
				if(po < N) {
					A[d][x][k] = a[d][po - (10 - x)];
					B[d][x][k] = b[d][po - (10 - x)];
					continue;
				}


				ll ans = 0;
				//First reduce roughly po/10
				ans += (po/10)/9;
				if(x == 9) {
					++ans;
				}
				ll las = x+1;
				if(las == 10) las = 1;

				for(int i = 8; i >= 0; --i) {
					ans += A[max(d, i)][las][k-1];
					las = B[max(d, i)][las][k-1];
					las = las + 10;
					if(las == 10 && i > 0) {
						++ans;
						las = 10 - max(d, i);
					}
				}
				las = las - 10;
				if(las == -10) las = 0;
				A[d][x][k] = ans;
				B[d][x][k] = las;
			}
		}
	}


	int t;
	cin >> t;
	while(t > 0) {
		--t;
		ll x;
		cin >> x;
		
		ll k = 0;


		for(ll bit = 62; bit >= 0; --bit) {
			ll ne = k + (((ll) 1) << bit);
			if(calc(0, ne) >= x) continue;
			k = ne;
		}
		++k;
		cout << k << "\n";

/*
		po = 1;
		for(int i = 1; i <= 16; ++i) {
			po *= 10;
		}

		for(ll j = 16; j >= 0; --j) {
			for(ll d = 9; d >= 0; --d) {
				ll ne = k + d*po;
				if(calc(0, ne) >= x) {
					continue;
				}
				k = ne;
			}
			po/=10;
		}

		++k;
		cout << k << "\n";
*/
	}












	return 0;
	for(int i = 1; i < M; ++i) {
		f[i] = INF;
		ll j = i;
		while(j > 0) {
			f[i] = min(f[i], f[i - j%10] + 1);
			j /= 10;
		}
	}


	for(int i = 1; i < M; ++i) {
		if(i == 10100) {
			cout << calc(0, i) << " " << f[i] << "\n";
		}
		if(calc(0, i) != f[i]) {
			cout << "Oh no!\n";
			cout << i << "\n";
			return 0;
		}
	}
	return 0;


/*
	for(int i = 1; i <= 2000; ++i) {
		out << i << " " << calc(0, i) << "\n";
	}
*/
/*	
	int n;
	cin >> n;
	cout << calc(0, n) << "\n";
*/
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED