CSES - Datatähti 2018 alku - Results
Submission details
Task:Kyselyt
Sender:lewski
Submission time:2017-10-11 22:35:36 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED25
#3ACCEPTED63
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.04 s2details
#3ACCEPTED0.05 s3details

Code

// 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 details

Test 1

Group: 1

Verdict: ACCEPTED

input
1000
582
214
723
273
...

correct output
0
1
7
7
6
...

user output
0
1
7
7
6
...
Truncated

Test 2

Group: 2

Verdict: ACCEPTED

input
1000
615664
916441
627600
279508
...

correct output
1
2
3
2
2
...

user output
1
2
3
2
2
...
Truncated

Test 3

Group: 3

Verdict: ACCEPTED

input
1000
672274832941907421
260504693279721732
646999966092970935
100853063389774434
...

correct output
7
2
2
0
9
...

user output
7
2
2
0
9
...
Truncated