Numerot

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll l[33][11], r[33][11][11], v[33][11][11], vas[111], ky[33], ysi[33], ra[33][11][11][11], va[33][11][11][11];
ll x, x1;
 
unsigned long long big = 9000000000000000000;
 
map<ll, ll> ma;
 
ll f(ll a){
    ll b=1;
    while ((a/ky[b])%10==9) b++;
    //cout << "tasa " << b << " " << ky[b] << " " << (a/ky[b]) << " " << (a/ky[b])%10 << " " << a <<"\n";
    x1=(a/ky[b])%10;
    ll c=0;
    for (ll i=max(b+1,(ll)2); i<=18; ++i){
 
        c = max(c, (a/ky[i])%10);
    }
    x=c;
    return b;
}
 
ll askeleet(ll a){
    //cout << a << " a\n";
    if (ma[a]) return ma[a];
    if (a<100){
        return vas[a];
    }
    ll a1=a;
    ll a2=f(a);
    ll c=a%(100), ans=0;
    if (a2>2) x=9;
    if (a2==2) x=max(x, x1);
    //cout << a << " " << x << " " << x1 << " " << ans << " " << c << " " << a2 << "\n";
    while (c>=0){
        ll d=c%10, e=(c/10)%10;
        c = c - max(x, max(d, e));
        ans++;
    }
    a = (a/100)*100 + c;
    ll viim=a%10;
    //cout << a << " " << viim << " " << ans << "\n";
    while (true){
        ll b=f(a);
        if (x==0 && x1==0) break;
        if (x==0){
            ans = ans + r[b][x1][viim];
            a = (a/ky[b]-1)*ky[b] + ysi[b] + v[b][x1][viim];
            viim=a%10;
        }
        else{
            ans = ans + ra[b][x][x1][viim];
            a = (a/ky[b+1]-1)*ky[b+1] + ysi[b+1] + va[b][x][x1][viim];
            viim=a%10;
        }
        //cout << a << " " << b << " " << x << " " << x1 << " " << ans << " " << viim << " " << ysi[b] << " " << v[b][x1][viim] << " \n";
    }
    //cout << a << " " << viim << " " << ans << "\n";
    ll b=f(a);
    ans+=l[b][viim];
    //cout << a << " " << b << " " << viim << " " << l[b][viim] << " " << ans << "\n";
    ma[a1]=ans;
    return ans;
}
 
 
int main(){
    ll t;
    cin >> t;
    ky[0]=1;
    ysi[2]=90;
    for (ll i=1; i<=18; ++i) ky[i]=ky[i-1]*10;
    for (ll i=3; i<=18; ++i) ysi[i] = 9*ky[i-1]+ysi[i-1];
    for (ll i=1; i<=100; ++i){
        ll a=0;
        a = max(a, i%10);
        a = max(a, (i/10)%10);
        vas[i]=vas[i-a]+1;
    }
    l[2][1]=l[2][2]=l[2][3]=15;
    for (ll i=4; i<=9; ++i) l[2][i]=16;
    for (ll k=1; k<=9; ++k){
        for (ll j=1; j<=9; ++j){
            ll a=90+j;
            ll b=0;
            while (a>=0){
                ll d=a%10, e=(a/10)%10;
                a = a - max(k, max(d, e));
                b++;
            }
            a+=10;
            r[2][k][j]=b;
            v[2][k][j]=a;
        }
    }
    for (ll i=3; i<=18; ++i){
        for (ll k=1; k<=9; ++k){
            for (ll j=1; j<=9; ++j){
                ll a=0, b=j;
                for (ll m=9; m>=0; --m){
                    ll c=max(k, m);
                    a+=r[i-1][c][b];
                    b = v[i-1][c][b];
                }
                r[i][k][j]=a;
                v[i][k][j]=b;
            }
        }
    }
    for (ll i=3; i<=18; ++i){
        for (ll j=1; j<=9; ++j){
            ll a=0, b=j;
            for (ll m=9; m>=1; --m){
                a+=r[i-1][m][b];
                b=v[i-1][m][b];
            }
            a+=l[i-1][b];
            l[i][j]=a;
        }
    }
    for (ll i=2; i<=18; ++i){
        for (ll k=1; k<=9; ++k){
            for (ll l=0; l<=8; ++l){
                if (k==0 && l==0) continue;
                for (ll j=1; j<=9; ++j){
                    ll a=0, b=j;
                    for (ll m=l; m>=0; --m){
                        a+=r[i][max(k, m)][b];
                        b =v[i][max(k, m)][b];
                    }
                    ra[i][k][l][j]=a;
                    va[i][k][l][j]=b;
                }
            }
        }
    }
    while (t--){
        ll y;
        cin >> y;
        if (y==1) {
            cout << "1\n";
            continue;
        }
        ll a=1;
        while (true){
            unsigned long long a1=(unsigned long long)a*2;
            if (a1>=big) break;
            if (askeleet(a*2)>=y) break;
            a=a*2;
            //cout << a << " " << a1 << "\n";
        }
        ll b=a;
        //cout << a << " " << b << "\n";
        while (a>=1){
            unsigned long long a1=(unsigned long long)(b + a);
            if (a1<big){
                if (askeleet(b+a)<y) b = b+a;
            }
            a/=2;
            //cout << a << " " << b << "\n";
        }
        cout << b+1 << "\n";
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED