Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 请问，我的第一个程序与第二个程序有差别吗？为什么第一个AC，第二个WA（所有差别都在前9行，其余完全一样），大牛指教啊！！

Posted by jiyanmoyu at 2009-08-19 15:02:11 on Problem 1095 and last updated at 2009-08-19 15:02:40
```AC的：
#include<iostream>
using namespace std;
#include<algorithm>

int h[]={1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700,1767263190};
int nIndex[]={1,2,4,9,23,65,197,626,2056,6918,23714,82500,290512,1033412,3707852,13402697,48760367,178405157,656043857};
const int hLength=sizeof(h)/sizeof(int);
const int nIndexLength=sizeof(nIndex)/sizeof(int);

void output(int n,int nodes)
{
if(0==n)
return;
if(1==n)
{
cout<<"X";
return;
}
int rest=n-nIndex[nodes-1];
int left=0,right=nodes-1;
while(rest-h[left]*h[right]>=0)
{
rest-=h[left]*h[right];
++left;
--right;
}
int leftIndex=rest/h[right]+nIndex[left-1],rightIndex=rest%h[right]+nIndex[right-1];
if(left!=0)
{
cout<<"(";
output(leftIndex,left);
cout<<")";
}
cout<<"X";
if(right!=0)
{
cout<<"(";
output(rightIndex,right);
cout<<")";
}
}

int main()
{
int n,myNodes;
while(cin>>n&&n!=0)
//    for(n=499000000;n<=500000000;++n)
{
myNodes=upper_bound(nIndex,nIndex+nIndexLength,n)-nIndex;
output(n,myNodes);
cout<<endl;
}
return 0;
}

WA的：
#include<iostream>
using namespace std;
#include<algorithm>

long h[]={1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700,1767263190,6564120420};
long nIndex[]={1,2,4,9,23,65,197,626,2056,6918,23714,82500,290512,1033412,3707852,13402697,48760367,178405157,656043857,2423307047,8987427467};
const int hLength=sizeof(h)/sizeof(long);
const int nIndexLength=sizeof(nIndex)/sizeof(long);

void output(int n,int nodes)
{
if(0==n)
return;
if(1==n)
{
cout<<"X";
return;
}
int rest=n-nIndex[nodes-1];
int left=0,right=nodes-1;
while(rest-h[left]*h[right]>=0)
{
rest-=h[left]*h[right];
++left;
--right;
}
int leftIndex=rest/h[right]+nIndex[left-1],rightIndex=rest%h[right]+nIndex[right-1];
if(left!=0)
{
cout<<"(";
output(leftIndex,left);
cout<<")";
}
cout<<"X";
if(right!=0)
{
cout<<"(";
output(rightIndex,right);
cout<<")";
}
}

int main()
{
int n,myNodes;
while(cin>>n&&n!=0)
//    for(n=499000000;n<=500000000;++n)
{
myNodes=upper_bound(nIndex,nIndex+nIndexLength,n)-nIndex;
output(n,myNodes);
cout<<endl;
}
return 0;
}```

Followed by: