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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:130: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:134:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         std::scanf("%zd", &i);
                              ^

Code

#include <array>
#include <cstdio>
#include <string>
#include <vector>

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()
{
    int 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');
    }
}

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
...

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
...

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
...