Problem B
Number Sequence
Input: standard input
Output: standard output
Time Limit: 1 second

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S₁S₂…S_k. Each group S_k consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. For example, the first 80 digits of the sequence are as follows:

11212312341234512345612345671234567812345678912345678910123456789101112345678910

Input

The first line of the input file contains a single integer t (1 <=t <=25), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 <=i <=2147483647)

 

Output

There should be one output line per test case containing the digit located in the position i.

 

Sample Input                           Output for Sample Input

2 8 3

2 2

---

做法 : 建出一部份的123456 ... n
之後二分查找

#include <stdio.h>
#include <math.h>

long long NLoc[33001];
char Sequ[1000000];
void Build() {
    int i, length, totlen = 0;
    char *s = Sequ;
    NLoc[0] = 0;
    for(i = 1; i <= 33000; i++) {
        sprintf(s, "%d", i);
        length = (int)log10(i)+1;
        s += length;
        totlen += length;
        NLoc[i] = totlen + NLoc[i-1];
    }
}
void FindNSeq(int v) {
    int l = 0, r = 33000, m;
    do {
        m = (l+r)>>1;
        if(NLoc[m] < v) {
            if(NLoc[m+1] >= v)
                break;
            else
                l = m+1;
        } else
            r = m-1;
    } while(l <= r);
    printf("%c\n", Sequ[v-NLoc[m]-1]);
}
int main() {
    Build();
    int T, i;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &i);
        FindNSeq(i);
    }
    return 0;
}