Solution to POJ 1019

The problem is on here.

Analysis

If we want to know what digit is on specified position, we need to locate the
which contains what we want, and further need to locate the in which contains
what we want, and finally the k in . As a result, we need
the length of and the length of
.

We can firstly calculate some of , and then the
until the maximum value less than
INT_MAX.
We can use this predication to examine the overflow of add operator: sum + k < sum. As the arrays containing and are naturally sorted, we can use binary search to improve the performance. Finally, we just need to know the digit in specified position of a number k. It’s a easy job and can be approached by converting k into string and seek its specified position.

Solution

After some experiences, I know only first 31267 of need to be calculated.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>

using namespace std;

const int MaxNumberCountByBit[] = {
    0, 9, 90, 900, 9000, 90000, 900000, 9000000, 90000000, 900000000
};
const int MinNumberByBit[] = {
    0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000
};

const int MaxK = 31267;
int LengthOfSkTable[MaxK + 1] = { 0 };
int LengthOfSSkTable[MaxK + 1] = { 0 };

int GetNumberBits(int number)
{
    int bits = 0;
    for(; number; number /= 10) {
        bits++;
    }
    return bits;
}

int LengthOfSk(int k)
{
    int bits = GetNumberBits(k);
    int sum = 0;
    for (int i = 1; i < bits; i++) {
        sum += i * MaxNumberCountByBit[i];
    }
    sum += (k - MinNumberByBit[bits] + 1) * bits;
    return sum;
}

void Initialize(void)
{
    for (int k = 1, sum = 0; k <= MaxK; k++) {
        int l = LengthOfSk(k);
        LengthOfSkTable[k] = l;
        LengthOfSSkTable[k] = (sum += l);
    }
}

int Solve(int position)
{
    int *previousSSkLengthIt = lower_bound(&LengthOfSSkTable[1], &LengthOfSSkTable[MaxK + 1], position) - 1;
    int positionInSk = position - *previousSSkLengthIt;

    int *previousSkLengthIt = lower_bound(&LengthOfSkTable[1], &LengthOfSkTable[MaxK + 1], positionInSk) - 1;
    int positionInKK = positionInSk - *previousSkLengthIt;
    int kk = distance(&LengthOfSkTable[0], previousSkLengthIt) + 1;

    stringstream ss;
    ss << kk;
    char number = ss.str().at(positionInKK - 1);

    return number - '0';
}

int main(void)
{
    Initialize();

    int t;
    cin >> t;
    while (t--) {
        int i;
        cin >> i;
        cout << Solve(i) << endl;
    }

    return 0;
}