Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

有什么特殊数据吗?我用穷举没有超时但WA 了

Posted by yygy at 2008-11-20 19:19:46 on Problem 1965
#include<stdio.h>
#include<string.h>
int root[70];
char s[200];
int isnotzero(int sum[],int n)
{
	int i;
	for(i=n-1;i>=0&&sum[i]==0;i--);
	if(i<0)
		return 0;
	return i;
}
int my_strcmp(char cube[],char s[])
{
	if(strlen(cube)<strlen(s))
		return -1;
	if(strlen(cube)==strlen(s))
	{
		if(strcmp(cube,s)<=0)
			return -1;
	}
	return 1;
}
void multi(int sum[],int temp[],int len)
{
	int i,j,k,c,e,n;
	i=isnotzero(temp,200);
	for(e=c=0;e<=i;e++,c++)
	{
		for(k=c,j=0;j<=len;k++,j++)
		{
			sum[k]+=temp[e]*root[j];
			n=k;
			while(sum[n]>9)
			{
				sum[n+1]+=sum[n]/10;
				sum[n]%=10;
				n++;
			}	
		}
	}
}
int cubes()
{
	int i,temp[200],len,sum[200],j;
	char cube[200];
	len=isnotzero(root,70);
	memset(temp,0,sizeof(temp));
	for(i=len;i>=0;i--)
		temp[i]=root[i];
	memset(sum,0,sizeof(sum));
	multi(sum,temp,len);
	len=isnotzero(sum,200);
	for(;len>=0;len--)
		temp[len]=sum[len];
	len=isnotzero(root,70);
	memset(sum,0,sizeof(sum));
	multi(sum,temp,len);
	len=isnotzero(sum,200);
	for(j=0;len>=0;len--,j++)
		cube[j]=sum[len]+'0';
	cube[j]='\0';
	if(my_strcmp(cube,s)<=0)
		return 1;
	return 0;
}
int main()
{
	int i,len,sum;
	while(scanf("%s",s)!=EOF)
	{
		if(strcmp(s,"0")==0)
		{
			printf("0 0.0000000000\n");
			continue;
		}
		memset(root,0,sizeof(root));
		len=strlen(s);
		for(i=0;i<30;i++,len++)
			s[len]='0';
		s[len]='\0';
		sum=0;
		for(i=len/3+2;i>=0;i--)
		{
			while(1)
			{
				root[i]++;
				if(cubes())
					continue;
				else
				{
					root[i]--;
					break;
				}
			}
			sum+=root[i];
		}
		sum%=10;
		len=isnotzero(root,70);
		i=len+1;
		printf("%d ",sum);
		if(i<=10)
		{
			printf("0.");
			i=10-len+1;
			while(i--)
				printf("0");
			for(;len>=0;len--)
				printf("%d",root[len]);
			printf("\n");
		}
		else
		{
			for(;len>=10;len--)
				printf("%d",root[len]);
			printf(".");
			for(;len>=0;len--)
				printf("%d",root[len]);
			printf("\n");
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator