Task: | Kyselyt |
Sender: | lewski |
Submission time: | 2017-10-11 22:35:36 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 25 |
#3 | ACCEPTED | 63 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.05 s | 1 | details |
#2 | ACCEPTED | 0.04 s | 2 | details |
#3 | ACCEPTED | 0.05 s | 3 | details |
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; // counterfor (; i > v[c - 1].second; c++) {} // increment counter for every changing point the index is larger thanconst 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 storedconst 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 numbersconst int r = t % c; // remainder of t / c, used to find the correct number in d// find and return the correct number using the remainderif (r != 0) {return d.at(r - 1);}// return the last number of d if the remainder is 0return d.back();}int main() {std::vector<std::pair<unsigned long long, unsigned long long>> v;std::string n = "9"; // changing points in the stringv.push_back(std::make_pair(9, 9));// add every changing point to the vectorfor (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 functionn += "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 doneint 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 indicesfor (int i = 0; i < q; ++i) {std::cin >> x;// the formula isn't needed for indices under 10 as they contain the index itselfif (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 |