BZOJ 1263 整数划分

Description

Input

Output

Sample Input

Sample Output

Hint

小学奥数结论题，尽可能地拆\(3\)即可，最后省\(4\)时拆成\(2\)与\(2\)（\(2 \times 2 > 3 \times 1\)）。

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

int n;

struct node

{

	short a[10010],l;

	node()

	{

		memset(a,0,sizeof(a));

		l = 1;

	}

	friend inline node operator *(int x,node &y)

	{

		node ret; ret.l = y.l+1;

		for (int i = 1;i <= y.l;++i)

		{

			ret.a[i] += y.a[i]*x;

			ret.a[i+1] += ret.a[i]/10;

			ret.a[i] %= 10;

		}

		if (ret.a[ret.l] == 0) ret.l--;

		return ret;

	}

	inline void print()

	{

		printf("%d\n",l);

		int t = 0;

		for (int i = l;i >= 1;--i)

		{

			printf("%d",this->a[i]);

			if (++t == 100) break;

		}

	}

}ans;

int main()

{

	freopen("1263.in","r",stdin);

	freopen("1263.out","w",stdout);

	scanf("%d",&n); ans.a[1] = 1;

	while (n)

	{

		if (n > 4) n -= 3,ans = 3*ans;

		else if (n == 4) n-= 4,ans = 4*ans;

		else ans = n*ans,n = 0;

	}

	ans.print();

	fclose(stdin); fclose(stdout);

	return 0;

}