记录编号	131578	评测结果	AAAAAAAAAA
题目名称	最优分解方案II	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2014-10-24 17:16:32	内存使用	0.32 MiB

#include<cstdio>
#include<cstring>
using namespace std;
struct dx
{
	int hs;
	int hw;
	int lk;
};
dx fr[1001];
int n,jl;
int a[1001],b[1001],c[2001];
void change(int,int []);
void cf();
int main()
{
	freopen("maxmul.in", "r", stdin);
	freopen("maxmul.out", "w", stdout);
	scanf("%d",&n);
	if(n==3)
	{
		printf("1 2\n2");
		return 0;
	}
	if(n==4)
	{
		printf("1 3\n3");
		return 0;
	}
	fr[1].hs=1;fr[1].hw=4;fr[1].lk=1;
	fr[2].hs=5;fr[2].hw=8;fr[2].lk=2;
	int i=3;
	while(1)
	{
		fr[i].hs=fr[i-1].hw+1;
		fr[i].hw=fr[i].hs+i+1;
		fr[i].lk=i;
		if(fr[i].hw>=n) 
		{
			jl=i;
			break;
		}
		i++;
	}
	if(n<=8) jl=2;
	if(n==fr[jl].hw)
	{
		a[0]=1;
		a[1]=1;
		for(int i=3;i<=jl+1;i++)
		{
			change(i,b);
			printf("%d ",i);
			cf();
		}
		change(jl+3,b);
		printf("%d",jl+3);
		cf();
		printf("\n");
		for(int i=a[0];i>=1;i--) printf("%d",a[i]);
		return 0;
	}
	int en=jl+2;
	int bj=en-(n-fr[jl].hs);
	a[0]=1;
	a[1]=1;
	for(int i=2;i<=en;i++)
	{
		if(i==bj) continue;
		change(i,b);
		printf("%d ",i);
		cf();
	}
	printf("\n");
	for(int i=a[0];i>=1;i--) printf("%d",a[i]);
	return 0;
}
void change(int x,int a[])
{
	for(int i=0;i<=a[0];i++) a[i]=0;
	while(x)
	{
		a[++a[0]]=x%10;
		x/=10;
	}
}
void cf()
{
	int i,j,x=0;
	for(i=1;i<=a[0];i++)
	{
		x=0;
		for(j=1;j<=b[0];j++)
		{
			c[i+j-1]+=a[i]*b[j]+x;
			x=c[i+j-1]/10;
			c[i+j-1]%=10;
		}
		c[i+b[0]]=x;
		x=0;
	}
	i=a[0]+b[0];
	while((c[i]==0)&&(i>1)) --i;
	c[0]=i;
	memset(a,0,sizeof(a));
	for(int k=i;k>=0;--k) a[k]=c[k];
	memset(c,0,sizeof(c));
}