2084233_ac_46ms_160k.cc

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <iostream>

using namespace std;
long N;
long n[] = {0,1,3,8,22,64,196,625,2055,6917,23713,82499,290511,1033411,3707851,13402696,48760366,178405156,656043856};

void f(long m)
{
	int i, j;

	if(m == 0);
	else if(m == 1){ cout << 'X';}
	else if(m == 2){ cout << "X(X)";}
	else if(m == 3){ cout << "(X)X";}
	else if(m == 4){ cout << "X(X(X))";}
	else if(m == 5){ cout << "X((X)X)";}
	else if(m == 6){ cout << "(X)X(X)";}
	else if(m == 7){ cout << "(X(X))X";}
	else if(m == 8){ cout << "((X)X)X";}
	else
	{
	for(i = 0; i < 19; i++)
		if(m<=n[i])
			break;
	if(m<=2*n[i-1]-n[i-2])
	{
		printf("X(");
		f(m-n[i-1]+n[i-2]);
		printf(")");
	}
	else
		if(m>n[i]-(n[i-1]-n[i-2]))
		{
			printf("(");
			f(n[i-1]-n[i]+m);
			printf(")X");
		}
		else
		{
			long sum;
			sum =2*n[i-1] - n[i-2];
			for(j=1; j<i; ++j){
				if(m>sum+(n[j]-n[j-1])*(n[i-j-1]-n[i-j-2])){
					sum +=(n[j]-n[j-1])*(n[i-j-1]-n[i-j-2]);
				}else break;
			}
			int l=1;
			while((sum+l*(n[i-j-1]-n[i-j-2]))<m) l++;
			cout<<'(';
			f(l+n[j-1]);
			cout << ")X(";
			f(m-sum-(l-1)*(n[i-j-1]-n[i-j-2])+n[i-j-2]);
			cout <<")";
		}
	}
}

void input()
{
	while(scanf("%ld",&N)==1&&N)
	{
		f(N);
		printf("\n");
	}
}

int main()
{
	input();
	return 1;
}