记录编号	33574	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 最优分解方案	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2011-11-11 13:23:59	内存使用	0.27 MiB

#include <iostream>  
#include <fstream>
#include <cstdio>   
#include <cstdlib>   
#include <cmath>   
#include <cstring>   
#include <string>   
#include <algorithm>   
#include <iomanip>   
using namespace std;  
int a[100],b,c,d,t,s=2,k1,k2,r[1001]={0};
string str,st;
void cheng(string &str1,string str2)
{
	int e,l,m,n,p,q,v[10000]={0},u[100],w[100],x,y,z;
	string stri;
	m=str1.length();
	n=str2.length();
	m--;
	n--;
	v[m+n]=0;
	for (p=0;p<=m;p++)
		u[p]=(int)str1[m-p]-'0';
	for (p=0;p<=n;p++)
		w[p]=(int)str2[n-p]-'0';
	for (p=0;p<=m;p++)
		for (q=0;q<=n;q++)
		{
			x=u[p]*w[q];
			y=x/10;
			z=x%10;
			l=p+q;
			v[l]=v[l]+z;
			v[l+1]=v[l+1]+v[l]/10+y;
			v[l]=v[l]%10;
		}
	e=m+n;
	if (v[m+n+1]!=0) e++;
	for (e=e;e>=0;e--)
		if (v[e]!=0) break;
	p=e;
	for (e=p;e>=0;e--) 
		stri+=(v[e]+'0');
	str1=stri;
}
int main(void)   
{   
	freopen ("best.in","r",stdin);
	freopen ("best.out","w",stdout);
	cin>>b;
	for (c=3;c<100;c++)
	{
		s+=c;
		r[s]=c-1;
		if (s>1000) break;
	}
	str="1";
	for (c=1;c<=1000;c++)
		if (r[c]==0) r[c]=r[c-1];
	if (b<=4) cout<<b;
		else 
		{
			for (c=b-1;c>=0;c--)
				if (r[c]!=r[b]) break;
			s=2;
			c++;
			for (d=0;d<r[b];d++)
			{
				a[d]=s;
				s++;
			}
			c=b-c;
			d=c%r[b];
			c=c/r[b];
			for (t=0;t<r[b];t++) a[t]+=c;
			for (t=r[b]-1;t>=0;t--)
			{
				if (d==0) break;
				a[t]++;
				d--;
			}
			for (t=0;t<r[b];t++)
			{
				k1=a[t]%10;
 				k2=a[t]/10;
				st="\0";
				if (k2==0) st+=(k1+'0');
					else 
					{
						st+=(k2+'0');
						st+=(k1+'0');
					}
				cheng(str,st);
			}
			cout<<str;
		}
  	fclose(stdin);
	fclose(stdout);
	return 0;   
}