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

怎么可能超时啊!

Posted by sunpy at 2008-08-06 22:22:27 on Problem 1416
#include<stdio.h>
#include<string.h>

#define N 7
#define M 1000000
char a[N];//store the number to be shreding
int store[N],s[N];//store the final result
int  appear[M];
int max,target,n,nparts;

int get_num(int n,int spos)
{
	int sum=0;
	while(n--)
	{
		sum=sum*10+a[spos]-'0';
		spos++;
	}
	return sum;
}
void add(int len)
{
	int i;
	int tempart[N],num,spos;
	spos=num=0;
	for(i=0;i<len;i++)
	{
		tempart[i]=get_num(s[i],spos);
		num+=tempart[i];
		spos=spos+s[i];
	}
	//for(int f=0;f<len;f++)
		//printf("%d ",tempart[f]);
	//printf("%d\n",num);
	if(max<=num&&num<=target)
	{
		nparts=len;
		max=num;
		appear[max]++;
		//printf("%d %d",max,appear[max]);
		memcpy(store,tempart,sizeof(tempart));
	}
	return;
}

void dfs(int remain_len,int parts)
{
	int i;
	if(remain_len==0)
		add(parts);
	else
		for(i=1;i<=remain_len;i++)
		{
			s[parts]=i;//store the length of each part
			dfs(remain_len-i,parts+1);
		}
	return;
}



int main()
{
	int n;
	while(scanf("%d %s",&target,a))
	{
		//printf("%s\n",a);
		if(target==0&&a[0]==0)
			break;
		memset(appear,0,sizeof(appear));
		nparts=max=0;
		n=strlen(a);
		dfs(n,0);
		if(max==0)
			printf("error\n");
		else if(appear[max]>1)
			printf("rejected\n");
		else
		{
			printf("%d",max);
			for(int i=0;i<nparts;i++)
				printf(" %d",store[i]);
			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