[UVA] 10706 - Number Sequence
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 S1S2…Sk. Each group Sk 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;
}