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