C++程序练习-1019: Number Sequence-建表

描述
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
输入
The first line of the input file contains a single integer t (1 ≤ t ≤ 10), 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)
输出
There should be one output line per test case containing the digit located in the position i.
样例输入
2
8
3样例输出
2
2
问题分析：
先找规律，可以发现数列排成梯形。首先初想建表，算下数据大小，发现表规模不是很大，不超过4w，且为O(1)。
算法：
1.建表
2.输入测试数据
3.根据表数据，计算输出结果

//冰非寒([e-mail])
//520kB 0ms 1309 B G++ 
#include <cstdio>
using namespace std;
//global variables
const int N = 31270;
int N9T[]={9,99,999,9999,999999};
unsigned long map[N];
int map_size = 0;
//functions
void init();
int getposition(int,int);
void print(unsigned long);
//main function
int main(){
	int cases;
	unsigned long n;
	init();
	scanf("%d",&cases);
	while(cases --){
		scanf("%u",&n);
		print(n);
	}
    return 0;
}
//initialize map
void init(){
	int i(0),j(0),t(0),k(1);
	unsigned long sum(0);
	int N9 = N9T[0];
	for(i = 1;sum <= 2147483647;++ i){
		map[i] = t + k;
		t = map[i];
		sum += map[i];
		if(i == N9){
			N9 = N9T[k];
			k ++;
		}
	}
	map_size = i;
}
//print result
void print(unsigned long n){
	int i(0),t(0),k(0),j(0);
    //find the position and value of map which n is in
	for(i = 1;i <= map_size;++ i){
		if(n > map[i]){
			n -= map[i];
		}else{
			break;
		}
	}
	for(i = 0;i <= map_size;++ i){
		if(n <= map[i]){
			j = map[i];
			k = i;
			break;
		}
	}
	//if n is less than ten directly output
	if(n < 10){
		printf("%u\n",n);
		return;
	}
    //else calculate the position
	t = j - n;
	printf("%d\n",getposition(k,t));
}
int getposition(int n,int p){
    int an[10]={0};
	int j = 0;
	while(n){
		an[j ++] = n % 10;
		n /= 10;
	}
	return an[p];
}