记录编号	69972	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 最优分解方案	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2013-09-22 19:59:33	内存使用	0.43 MiB

#include <fstream>
using namespace std;
ifstream fi("best.in");
ofstream fo("best.out");
int n,a[1001],w,b[10001],bw,c[10001],cw,p[10001],pw;
void init()
{
	int s=2,t=0,p=n,i;
	while (p>s)
	{
		a[++t]=s;
		p-=s;s++;
	}
	w=t;
	while (p>0)
	{
		a[t--]++;
		p--;
		if (t==0) t=w;
	}
	for (i=1;i<=10000;i++) b[i]=0;
	b[1]=1;bw=1;
}
void fj(int x)
{
	int i,t=0;
	for (i=1;i<=10000;i++) c[i]=0;
	cw=0;
	while (x!=0)
	{
		c[++t]=x%10;
		x/=10;cw++;
	}
}
void jh()
{
	int i,u[10001];
	for (i=1;i<=cw;i++)
		u[i]=c[i];
	for (i=1;i<=bw;i++)
		c[i]=b[i];
	for (i=1;i<=cw;i++)
		b[i]=u[i];
	cw=i;i=bw;bw=cw;
}
void jw()
{
	int i,o=0;
	pw=bw+cw-1;
	for (i=1;i<=pw;i++)
	{
		p[i]+=o;
		if (p[i]>9) {o=p[i]/10;p[i]%=10;}else
			o=0;
	}
	if (o!=0)
	{
		pw++;
		p[i]=o;
	}
}
void gjd()
{
	int i,j;
	if (cw>bw) jh();
	for (i=1;i<=10000;i++) p[i]=0;
	for (i=1;i<=cw;i++)
		for (j=1;j<=bw;j++)
			p[i+j-1]+=c[i]*b[j];
	jw();
	for (i=1;i<=pw;i++)
		b[i]=p[i];
	bw=i;i=pw;pw=bw;
}
int main()
{
	int i;
	fi>>n;
	init();
	for (i=1;i<=w;i++)
	{
		fj(a[i]);
		gjd();
	}
	i=bw;
	while (b[i]==0) i--;
	for (i=i;i>=1;i--) fo<<b[i];
	fo<<endl;
	return 0;
}