Task: | Kyselyt |
Sender: | eliaskosunen |
Submission time: | 2017-10-07 14:17:54 +0300 |
Language: | C++ |
Status: | READY |
Result: | 88 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | ACCEPTED | 25 |
#3 | ACCEPTED | 63 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.05 s | 1 | details |
#2 | ACCEPTED | 0.05 s | 2 | details |
#3 | ACCEPTED | 0.04 s | 3 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:185:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] std::scanf("%d", &q); ^ input/code.cpp:189:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] std::scanf("%zd", &i); ^
Code
#include <algorithm> #include <array> #include <cassert> #include <cstdio> #include <iostream> #include <map> #include <set> #include <string> #include <unordered_map> #include <vector> #ifdef LOCAL #include "slow.h" #endif std::size_t count_digits(std::size_t x) { // clang-format off return (x < 10u ? 1 : (x < 100u ? 2 : (x < 1000u ? 3 : (x < 10000u ? 4 : (x < 100000u ? 5 : (x < 1000000u ? 6 : (x < 10000000u ? 7 : (x < 100000000u ? 8 : (x < 1000000000u ? 9 : (x < 10000000000u ? 10 : (x < 100000000000u ? 11 : (x < 1000000000000u ? 12 : (x < 10000000000000u ? 13 : (x < 100000000000000u ? 14 : (x < 1000000000000000u ? 15 : (x < 10000000000000000u ? 16 : (x < 100000000000000000u ? 17 : (x < 1000000000000000000u ? 18 : (x < 10000000000000000000u ? 19 : 20))))))))))))))))))); // clang-format on } std::size_t pow10(std::size_t pow) { static std::array<std::size_t, 20> p = {{1u, 10u, 100u, 1000u, 10000u, 100000u, 1000000u, 10000000u, 100000000u, 1000000000u, 10000000000u, 100000000000u, 1000000000000u, 10000000000000u, 100000000000000u, 1000000000000000u, 10000000000000000u, 100000000000000000u, 1000000000000000000u, 10000000000000000000u}}; return p[pow]; } char get_digit(std::size_t number, std::size_t digit) { digit = count_digits(number) - digit - 1; return (number / pow10(digit)) % 10 + '0'; } std::size_t get_matching_pow10(std::size_t number) { return count_digits(number); } std::size_t get_next_pow10(std::size_t number) { return get_matching_pow10(number) + 1; } std::size_t numbers_with_length(std::size_t len) { return 9 * pow10(len - 1); } std::size_t digits_with_length(std::size_t len) { return numbers_with_length(len) * len; } std::size_t numbers_with_length_upto(std::size_t len) { static std::array<std::size_t, 20> store{ {9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; if (store[len - 1] == 0) { store[len - 1] = numbers_with_length_upto(len - 1) * 10 + 9; } return store[len - 1]; } std::size_t digits_with_length_upto(std::size_t len) { static std::array<std::size_t, 20> store{ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; if (store[len - 1] == 0) { store[len - 1] = ((9 * (pow10(len) * (len + 1))) - pow10(len + 1) + 1) / 9; } return store[len - 1]; } std::size_t digits_in_member(std::size_t n) { for (auto i = 0; i < 20; ++i) { if (digits_with_length_upto(i) >= n) { return i; } } return 20; } char digit(std::size_t n) { /* if (n < 10) { */ /* return n + '0'; */ /* } */ auto d = digits_in_member(n); auto digit_n = n - digits_with_length_upto(d - 1); auto ord = digit_n / d; if (digit_n % d != 0) { ++ord; } auto num = ord + numbers_with_length_upto(d - 1); return get_digit(num, (digit_n - 1) % d); } int main() { /* series_point s; */ /* assert(pow10(1) == 10); */ /* assert(pow10(2) == 100); */ /* std::cout << get_digit(13, 0) << ' ' << get_digit(13, 1) << '\n'; */ /* assert(get_digit(1, 0) == '1'); */ /* assert(get_digit(13, 1) == '3'); */ /* assert(series_point{}.get_char(1) == '1'); */ /* assert(series_point{}.get_char(10) == '1'); */ /* assert(series_point{}.get_char(11) == '0'); */ /* for (std::size_t i = 1; i <= 1010; ++i) { */ /* auto a = s.get_char(i); */ /* auto c = series_point{}.get_char(i); */ /* if (i % 29 == 0) { */ /* auto tmp = series_point{}; */ /* auto b = tmp.get_char(i); */ /* if (a != b) { */ /* std::cout << " * At i = " << i << ", a != b:\n" */ /* << " a = " << a << ", b = " << b << '\n' */ /* << " State of s (a): " << s << '\n' */ /* << " State of tmp (b): " << tmp << '\n'; */ /* } */ /* if(b != c) { */ /* std::cout << " * At i = " << i << ", b != c:\n" */ /* << " b = " << b << ", c = " << c << '\n' */ /* << " State of tmp (b): " << tmp << '\n'; */ /* } */ /* } */ /* } */ #if 0 for(std::size_t i = 1; i <= 200; ++i) { std::cout << slow::series_point{}.get_char(i) << '\t' << digit(i) << '\n'; } /* slow::series_point s{}; */ /* for (std::size_t i = 1; i <= 1010; ++i) { */ /* auto correct = s.get_char(i); */ /* auto test = digit(i); */ /* if (correct != test) { */ /* std::cout << " * At i = " << i << ", a != b:\n" */ /* << " correct = " << correct << ", given = " << test << '\n'; */ /* } */ /* } */ #else /* series_point s; */ int q; /* std::cin >> q; */ std::scanf("%d", &q); std::vector<std::size_t> inputs(q); for (auto& i : inputs) { std::scanf("%zd", &i); } std::vector<char> outputs(q); for (auto i = 0; i < q; ++i) { outputs[i] = digit(inputs[i]); } for (auto& o : outputs) { std::putchar(o); std::putchar('\n'); } #endif }
Test details
Test 1
Group: 1
Verdict: WRONG ANSWER
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 |