ZCMU-Problem C - Sumsets

Description

Problem C - Sumsets

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

Input

Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

Output

For each S, a single line containing d, or a single line containing "no solution".

Sample Input

Sample Output

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int main(){    int n,i,j,a[1001],sum,left,right,m;    while(~scanf("%d",&n))    {        if(n==0)            break;        memset(a,0,sizeof(a));        m=-1;        for(i=0;i<n;i++)        {            scanf("%d",&a[i]);        }        sort(a,a+n);//排序整个集合中的元素        for(i=n-1;i>=0;i--)//d的取值        {            for(j=n-1;j>=0;j--)//c的取值            {                if(i==j)                    continue;                sum=a[i]-a[j];//a+b的值                left=0,right=j-1;//从0开始到j-1寻找a和b的值                while(left<right)                {                    if(a[left]+a[right]==sum)                    {                        m=a[i];                    goto loop;                    }                    else if(a[left]+a[right]>sum)                    {                        right--;                    }                    else                    {                        left++;                    }                }            }        }        loop:        if(m==-1)            printf("no solution/n");//没有这样的值        else            printf("%d/n",m);    }    return 0;}