Kyselyt

// all positive integers are lined up in ascending order in The String, find the number at an index
// an increase of 1 raises the number's index in the string by 1 more than before at every changing point

#include <iostream>
#include <string>
#include <vector>


char z(const std::vector<std::pair<unsigned long long, unsigned long long>> v, unsigned long long i) {
  int c = 1; // counter
  for (; i > v[c - 1].second; c++) {} // increment counter for every changing point the index is larger than

  const unsigned long long t = i + c * v[c - 2].first - v[c - 2].second; // temp value, will be used in two calculations and therefore needs to be stored

  const std::string d = std::to_string((t + c - 1) / c); // temp value divided by counter and rounded up, std::ceil is not used due to possible large numbers
  const int r = t % c; // remainder of t / c, used to find the correct number in d

  // find and return the correct number using the remainder
  if (r != 0) {
    return d.at(r - 1);
  }

  // return the last number of d if the remainder is 0
  return d.back();
}


int main() {
  std::vector<std::pair<unsigned long long, unsigned long long>> v;
  std::string n = "9"; // changing points in the string

  v.push_back(std::make_pair(9, 9));

  // add every changing point to the vector
  for (int i = 1; i < 18; ++i) {
    // n = 9, 99, 999, ...
    // this could be done with std::pow if it weren't for the possible very large numbers
    // std::pow doesn't return unsigned long longs so I'd rather use a string than overload the function
    n += "9";
    // pair of n as unsigned long long and the index of n in The String (previous index + (current changing point - previous changing point) * number of current changing point)
    v.push_back(std::make_pair(std::stoull(n), v[i - 1].second + (stoull(n) - v[i - 1].first) * (i + 1)));
  }

  // get the number of queries to be done
  int q;
  std::cin >> q;

  unsigned long long x; // the index to find in The String

  // receive the queries and get the number at the queried indices
  for (int i = 0; i < q; ++i) {
    std::cin >> x;
    // the formula isn't needed for indices under 10 as they contain the index itself
    if (x < 10) {
      std::cout << x << '\n';
      continue;
    }
    std::cout << z(v, x) << '\n';
  }

  return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED