记录编号	34894	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 最优分解方案	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-01-17 16:16:35	内存使用	0.28 MiB

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;

const int MAXN=50;
int N;
int Num[MAXN];
int top=0;

class hugeint
{
public:
    int len,num[1000];
};

hugeint Tmp,Ans;
hugeint times(hugeint a,hugeint b)
{
    int i,j;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    for (i=1;i<=a.len;i++)
        for (j=1;j<=b.len;j++)
            ans.num[i+j-1]+=a.num[i]*b.num[j];
    for (i=1;i<=a.len+b.len;i++)
    {
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]=ans.num[i]%10;
    }
    if (ans.num[a.len+b.len]>0)
        ans.len=a.len+b.len;
    else
        ans.len=a.len+b.len-1;
    return ans;
}

void work()
{
	scanf("%d\n",&N);
	
	if(N==0)
	{
		printf("0\n");
		exit(0);
	}
	
	int Sum=0;
	int i;
	for (i=2;;i++)
	{
		Sum+=i;
		if(Sum>N)
			break;
	}
	for (int j=2;j<=i;j++)
		Num[++top]=j;
	
	int tmp=Sum-N;
	if(tmp==1)
		Num[1]=0,Num[top]++;
	else
		Num[tmp-1]=0;
//	printf("%d\n",tmp);
} 

void compute()
{
	memset(Ans.num,0,sizeof(Ans.num));
	Ans.len=1;
	Ans.num[1]=1;
	
	for (int i=1;i<=top;i++)
	{
		if(Num[i]==0)
			continue;
		int x=Num[i];
		
		Tmp.len=0;
		memset(Tmp.num,0,sizeof(Tmp.num));
		
		while(x)
		{
			Tmp.num[++Tmp.len]=x%10;
			x/=10;
		}
		
		Ans=times(Ans,Tmp);
	}
	
	for (int i=Ans.len;i>=1;i--)
		printf("%d",Ans.num[i]);
	printf("\n");
}
 
int main()
{
	freopen("best.in","r",stdin);
	freopen("best.out","w",stdout);
	work();
	compute();
	return 0; 
}