pku 1019 number sequence .txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
 
//PKU 1019 Number Sequence 
#define NMAX 50005

__int64 start[NMAX];//start[i],第i个数对应的起始点
__int64 one[NMAX];//one[i],第i个数对应区间的大小
int sjz[100];

int getwei(int num)
{
	int i=0;
	while(num>0)
	{
		i++;
		num/=10;
	}
	return i;
}

void getsjz(int num)
{
	int i=1;
	while(num>0)
	{
		sjz[i]=num%10;
		num/=10;
		i++;
	}
	sjz[0]=i-1;
}

void init()
{
	int i,j;
//	__int64 last=0;
	start[1]=1;
	one[1]=1;
	for(i=2;i<=40000;i++)
	{
		one[i]=getwei(i)+one[i-1];
		start[i]=start[i-1]+one[i-1];
//		printf("start[%d]=%I64d one=%I64d\n",i,start[i],one[i]);
	}
}

void solve(__int64 num)
{
	int i=1,j,k,ii,yushu;
	while(num>=start[i]) i++;
	j=num-start[i-1]+1;//该数区间的第j个数字
	k=1;
	ii=1;
	while(one[k]<j) k++;//第j个数字对应的数 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2，当j=10,11时，k=10；j=12,13时,k=11
	yushu=one[k]-j;//第j个数字具体对应数k的什么位置
	getsjz(k);
//	printf("start[%d]=%I64d j=%d k-1=%d yushu=%d\n",i-1,start[i-1],j,k-1,yushu);
	printf("%d\n",sjz[yushu+1]);
}

int main()
{
	int cnum,i;
	__int64 num;
	init();
	scanf("%d",&cnum);
	for(i=1;i<=cnum;i++)
	{
		scanf("%I64d",&num);
		solve(num);
	}
	return 0;
}