Numerot

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef uint64_t ll;

pair<ll, ll> dp[22][10][10][10];

ll ff(ll n) {
	if (n==0) return 0;
	if (n<10) return 1;
	ll fn=0;
	ll subs=0;
	ll k=1;
	ll lv=0;
	ll x=n/10;
	ll y=0;
	while (x){
		k*=10;
		if (lv==0){
			fn++;
			if (x%10!=0){
				lv=x%10;
				subs=lv*k;
			}
		} else {
			y=max(y, x%10);
		}
		x/=10;
	}
	assert(fn>0&&lv>0&&subs>=10);
	auto u = dp[fn][lv][n%10][y];
	n-=subs;
	n-=n%10;
	n+=(ll)u.S;
	return u.F+ff(n);
}

pair<ll, ll> fa(ll n, ll y, bool init) {
	if (n<10) return {0, n};
	ll fn=0;
	ll subs=0;
	ll k=1;
	ll lv=0;
	ll x=n/10;
	ll ny=y;
	ll ma=max(y, n%10);
	while (x){
		ma=max(ma, x%10);
		k*=10;
		if (lv==0){
			fn++;
			if (x%10!=0){
				lv=x%10;
				subs=lv*k;
			}
		} else {
			ny=max(ny, x%10);
		}
		x/=10;
	}
	assert(fn>0&&lv>0&&subs>=10);
	if (!init) {
		auto u = dp[fn][lv][n%10][ny];
		n-=subs;
		n-=n%10;
		n+=(ll)u.S;
		auto uu = fa(n, y, false);
		return {u.F+uu.F, uu.S};
	}
	if (ma>n%10){
		auto uu=fa(n-ma, y, false);
		return {1+uu.F, uu.S};
	} else {
		auto uu=fa(n-n%10, y, true);
		return {1+uu.F, uu.S};
	}
}

int f[1010101];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	for (int i=1;i<=1000000;i++){
		f[i]=i;
		int x=i;
		while (x){
			f[i]=min(f[i], f[i-x%10]+1);
			x/=10;
		}
	}
	for (int n=0;n<19;n++){
		for (int m=0;m<10;m++){
			for (int k=0;k<10;k++){
				for (int x=0;x<10;x++){
					if (n==0){
						dp[n][m][k][x]={0, k};
						continue;
					}
					ll num=m;
					for (int i=0;i<n;i++){
						num*=10;
					}
					num+=k;
					dp[n][m][k][x]=fa(num, x, true);
				}
			}
		}
	}
	int t;
	cin>>t;
	for (int i=0;i<t;i++){
		ll x;
		cin>>x;
		uint64_t mi=0;
		uint64_t ma=x*9;
		while (mi<=ma){
			uint64_t mid = (mi+ma)/2ull;
			ll y=ff(mid);
			if(y<x){
				mi=mid+1;
			} else {
				ma=mid-1;
			}
		}
		cout<<mi<<endl;
	}
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED