2402.txt

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

//#define debug 1
#define NMAX 30
#define INF 1000000001
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

int n;
__int64 a[NMAX];
void init()
{

	a[1]=9;
	a[2]=9;
	int i;
	int tsum=18;
	for(i=3;i<30;i++)
	{
		if(i%2)
			a[i]=10*a[i-1];
		else
			a[i]=10*a[i-2];
		tsum+=a[i];
	}
}
__int64 b[NMAX];
void solve()
{
	int i=2;
	if(n<=9)
	{
		printf("%d\n",n);
		return ;
	}
	if(n-9<=9)
	{
		printf("%d%d\n",n-9,n-9);
		return ;
	}

	__int64 tsum=9;
	while(!(n>tsum&&n<=tsum+a[i]))
	{
		tsum+=a[i++];
	}
	
	__int64 t=n-tsum-1;
	int len=i;
	if(len%2)
	{
		b[len/2+1]=t%10;
		t=t/10;
	}
	len/=2;
	for(;len>=2;len--)
	{
		b[len]=t%10;
		t/=10;
	}
	b[len]=t+1;
	
	for(int j=2;j<=len/2;j++)
	{
		b[j]=t/10;
		t%=9;
	}
	
	
	for(int k=1;k<=i/2;k++)
		printf("%I64d",b[k]);
	if(i%2)
		printf("%I64d",b[i/2+1]);
	for(k=i/2;k>=1;k--)
		printf("%I64d",b[k]);
	printf("\n");
}
main()
{
#if _DEBUG 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	init();
	while(1)
	{
		scanf("%d",&n);
		if(!n)
			break;
		solve();
	}
#if _DEBUG 
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}