1019.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

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

#define INF 30000
#define NMAX 52
unsigned int n;
int bit(unsigned int in)
{
	int i;
	
	i=0;
	while(in)
	{
		in/=10;
		i++;
	}
	return i;
}
unsigned int get(unsigned int m,unsigned int b)
{
	unsigned  int i;
	int t=bit(m);
	for(i=1;i<=t-b;i++)
	{
		m/=10;
	}
	return m%10;
}
void solve()
{
	
	unsigned int a=0,last=0;
	unsigned int i;
	unsigned int sum=1;
	for(i=1;;i++)
	{
		last=sum;
		a+=bit(i);
		sum+=a;
		
		if(sum>n)
			break;
	}
	unsigned int b;
	b=1;
	n=n-last+1;
	for(i=1;;i++)
	{
		last=b;
		b+=bit(i);
		if(b>n)
			break;
	}
	printf("%d\n",get(i,n-last+1));
}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
//		for(int i=9200;i<10000;i++)
//		{
//			n=i;
			solve();
//		}
	}
		
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}