Numerot

#include <iostream>
#include <functional>
using namespace std;
 
long S[20][10][10][10];
int L[20][10][10][10];
long ppow[20];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ppow[0] = 1;
    for (int j = 1; j < 19; ++j)
        ppow[j] = ppow[j - 1] * 10;
    ppow[19] = -1 ^ (1ll << 63);
 
    for (int b = 0; b <= 9; ++b) {
        for (int v = 0; v <= 9; ++v) {
            if (b > v) {
                S[0][b][v][v] = 0;
                L[0][b][v][v] = v;
            } else {
                S[0][b][v][v] = (v != 0);
                L[0][b][v][v] = 0;
            }
        }
    }
    auto step = [](long x, int b) {
        long r = b;
        long y = x;
        while (y) { r = max(r, y % 10); y /= 10; }
        return x - r;
    };
 
    function<pair<long, int>(long, int)> solve = [&](long n, int b) -> pair<long, int> {
        if (n < 10)
            return b > n ? make_pair(long(0), int(n)) : make_pair(long(n > 0), 0);
        int lpow = 1;
        while (n / ppow[lpow] % 10 == 0)
            lpow++;
        long s = 0;
        while (n / ppow[lpow] % 10 == step(n, b) / ppow[lpow] % 10) {
            n = step(n, b);
            s++;
        }
        int nb = b;
        for (int p = lpow + 1; p <= 18; ++p)
            b = max(b, int(n / ppow[p] % 10));
        int v = int(n / ppow[lpow] % 10);
        int m = int(n % 10);
        s += S[lpow][b][v][m];
        int lx = L[lpow][b][v][m];
        auto [sx, l] = solve(n - n % 10 + lx - v * ppow[lpow], nb);
        return make_pair(s + sx, l);
    };
 
    for (int pot = 1; pot <= 18; ++pot) {
        for (int v = 1; v <= 9; ++v) {
            for (int b = 0; b <= 9; ++b) {
                for (int m = 0; m <= 9; ++m) {
                    if (m >= max(v, b))
                        continue;
                    long num = ppow[pot] * v + m - max(v, b);
                    auto [s, l] = solve(num, b);
                    S[pot][b][v][m] = s + 1;
                    L[pot][b][v][m] = l;
                }
            }
        }
    }
 
 
    auto calc  = [&](long k) {
        long z = 0;
        for (long b = 1l << 62; b; b /= 2)
            if (solve(b + z, 0).first < k)
                z += b;
        return z + 1;
    };
 
    int t;
    cin >> t;
    while (t--) {
        long k;
        cin >> k;
        cout << calc(k) << '\n';
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED