Numerot

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
 
const int MAXDC = 20;
const int BASE = 10;
 
int pot[MAXDC+2];
pii dp[MAXDC][BASE][BASE][BASE];
 
struct Num {
  int val;
  Num(int x=0) : val(x) {}
  int operator[](int pos) const {
    return val / pot[pos] % 10;
  }
  int tzc() const {
    for (int i=2;; i++)
      if (val % pot[i] >= 10) return i-1;
  }
};
 
map<pii, pii> cache;
pii set_zeros(int k, int count) {
  pii cachekey(k, count);
  if (auto it=cache.find(cachekey); it!=cache.end())
    return it->second;
  int totsteps = 0;
  int totdec = 0;
  int maxdc = MAXDC;
  while (maxdc>0 && k<pot[maxdc-1]) maxdc--;
  for (;;) {
    int rem = k % pot[count];
    if (rem < 10 && totsteps) break;
    if (k < 10) break;
    int zc = Num(k).tzc();
    int maxd = 0;
    for (int i=zc+1, tmp=k/pot[zc+1]; maxd<9 && tmp; i++, tmp/=10)
      maxd = max(maxd, tmp%10);
    int first = Num(k)[zc];
    int last = k % 10;
    auto [steps, dec] = dp[zc][maxd][first][last];
    if (steps == 0) {
      steps = 1;
      dec = max(maxd, max(first, last));
    }
    totsteps += steps;
    totdec += dec;
    k -= dec;
    while (maxdc>0 && k<pot[maxdc-1]) maxdc--;
  }
  return pii(totsteps, totdec);
  //return cache[cachekey] = pii(totsteps, totdec);
}
 
int f(int k) {
  auto [steps, dec] = set_zeros(k, MAXDC);
  return steps + (k-dec>0);
}
 
int solve(int x) {
  int mink = x;
  int maxk = 9*x;
  int nextguess = -1;
  while (mink < maxk - 5) {
    if (nextguess == -1 || nextguess < mink || nextguess > maxk)
      nextguess = mink+(maxk-mink)/2;
    int y = f(nextguess);
    if (y < x) {
      mink = max(mink, nextguess + 1);
      nextguess += (x - y) * 8;
    }
    else {
      maxk = min(maxk, min(nextguess-1, nextguess-(y-x)/9));
    }
  }
  while (f(mink) < x) mink++;
  return mink;
}
 
void init() {
  pot[0] = 1;
  for (int i=1; i<MAXDC+2; i++)
    pot[i] = 10 * pot[i-1];
  for (int zc=1; zc<MAXDC; zc++) {
    for (int maxd=0; maxd<=9; maxd++) {
      for (int first=0; first<=9; first++) {
        for (int mod10=0; mod10<=9; mod10++) {
          int k = pot[zc+1]*maxd + pot[zc]*first + mod10;
          dp[zc][maxd][first][mod10] = set_zeros(k, zc);
        }
      }
    }
  }
}
 
signed main() {
  auto T0 = chrono::high_resolution_clock::now();
  auto ELAPSED = [&]() -> int {
    auto d = chrono::high_resolution_clock::now() - T0;
    return chrono::duration_cast<chrono::milliseconds>(d).count();
  };
  ios::sync_with_stdio(0);
  init();
  int t;
  cin >> t;
  for (int iter=0; t--; iter++) {
    if (ELAPSED() > 950 && iter<700) assert(0);
    int x;
    cin >> x;
    int k = solve(x);
    if (f(k) == x) {
      cout << k << '\n';
    }
    else {
      cout << "-1\n";
    }
  }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED