Numerot

input/code.cpp: In function 'int f(int)':
input/code.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < s.size(); ++i) {
                  ~~^~~~~~~~~~
input/code.cpp: In function 'std::pair<long long int, long long int> f_nines(ll)':
input/code.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < s.size(); ++i) {
                  ~~^~~~~~~~~~
input/code.cpp:93:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < s.size(); ++j) s[j] += '0';
                      ~~^~~~~~~~~~
input/code.cpp: In function 'll get_max(ll)':
input/code.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < s.size(); ++i) ma = max(ma, (ll)s[i]-'0');
                  ~~^~~~~~~~~~
input/code.cpp: In function 'll f2(ll)':
input/code.cpp:113:6: warning: unu...

#include <iostream>
#include <cassert>
#include <cmath>
#include <sstream>
#include <cstring>
using namespace std;
using ll = long long;
int dp[1000100];
 
int f(int n) {
  if(n == 0) return 0;
  if(dp[n] != -1) return dp[n];
  stringstream ss;
  ss << n;
  string s;
  ss >> s;
  dp[n] = 1e9;
  for(int i = 0; i < s.size(); ++i) {
    dp[n] = min(dp[n], f(n - (s[i] - '0')) + 1);
  }
  return dp[n];
}
// max_n, len, last_d
//                  len
// ...,max_n, ..., {9, ..., last_d}
//
// {steps, last_digit}
// to 
// ..., max_n, ..., {0, 0, 0, last_digit}
pair<ll, ll> dp2[10][20][10];
pair<ll, ll> fast_f(ll max_n, ll len, ll last_d) {
  if(dp2[max_n][len][last_d].first != -1) {
    return dp2[max_n][len][last_d];
  }
  ll last_d_copy = last_d;
  if(len == 1) {
    return make_pair(0ll, last_d);
  }
  ll steps = 0;
  for(ll i = 9; i >= 0; --i) {
    ll new_max_n = max(max_n, i);
    auto tmp = fast_f(new_max_n, len-1, last_d);
    if(i > 0) {
      steps += tmp.first;
      // i000x --> i000
      if(tmp.second >= new_max_n) {
        // note that new_max_n > 0
        ++steps;
        // i0000 - new_max_n
        // (i-1)999...
        last_d = 10 - new_max_n;
        ++steps;
      }
      // i000x --> (i-1)000y
      else {
        last_d = 10+tmp.second-new_max_n;
        ++steps;
      }
    }
    else {
      steps += tmp.first;
      dp2[max_n][len][last_d_copy] = {steps, tmp.second};
      return dp2[max_n][len][last_d_copy];
    }
  }
  assert(0);
}
int brute(int x) {
  for(int i = 1; ; ++i) {
    if(f(i) == x) return i;
  }
}
pair<ll, ll> f_nines(ll x) {
  stringstream ss;
  ss << x;
  string s;
  ss >> s;
  int max_n[20] = {0};
  for(int i = 0; i < s.size(); ++i) {
    s[i] -= '0';
    max_n[i+1] = max(max_n[i],(int) s[i]);
  }
  ll nn = s.size();
  ll nines = 0;
  for(int i = nn-2; i >=0; --i) {
    if(s[i] == 9) {
      s[i] = 0;
      ++nines;
    }
    else {
      auto x = fast_f(max_n[i+1], nines+1, s[nn-1]);
      s[nn-1] = x.second;
      for(int j = 0; j < s.size(); ++j) s[j] += '0';
      stringstream s2;
      s2 << s;
      ll out;
      s2 >> out;
      return {x.first, out};
      break;
    }
  }
}
ll get_max(ll x) {
  stringstream ss;
  ss << x;
  string s;
  ss>>s;
  ll ma = 0;
  for(int i = 0; i < s.size(); ++i) ma = max(ma, (ll)s[i]-'0');
  return ma;
}
ll f2(ll x) {
  ll q = 1;
  ll steps = 0;
  while(x > 0) {
    if(x < 10) {
      return steps + 1;
    }
    ll y = x/10;
    if(y %10 != 9) {
      x -= get_max(x);
      ++steps;
    }
    else {
      auto tmp = f_nines(x);
      x = tmp.second;
      steps += tmp.first;
    }
  }
}
int main() {
  memset(dp, -1, sizeof(dp));
  for(int i = 0; i < 10; ++i) {
    for(int j = 0; j < 20; ++j) {
      for(int k = 0; k < 10; ++k) {
        dp2[i][j][k] = {-1ll, 0ll};
      }
    }
  }
  int tt;
  cin>>tt; 
  for(int xx = 0; xx < tt; ++xx) {
    ll x;
    cin>>x;
    ll lo = 0;
    ll hi = 5e17;
    ll best = hi;
    while(lo <= hi) {
      ll mid = (lo+hi)/2;
      if(f2(mid) >= x) {
        hi = mid-1;
        best = mid;
      }
      else {
        lo = mid+1;
      }
    }
    cout<<best<<endl;
  }
}

Test 1

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED