1879.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1879 on 2006-10-01 at 01:47:26 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1024;

int s[N*N], sn;

int main()
{
	int n, e[N], i;

	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) scanf("%d", &e[i]);
		sort(e, e+n);
		for(i = sn = 0; i < n; i++)
			for(int j = i+1; j < n; j++) s[sn++] = e[i]+e[j];
		sort(s, s+sn);
		for(i = n-1; i >= 0; i--) {
			bool can = false;
			for(int j = i-1; j >= 0; j--) {
				int rd = e[i]-e[j], cnt;
				pair<int*, int*> er = equal_range(s, s+sn, rd);
				cnt = er.second-er.first;
				if(cnt == 0) continue;
				else if(cnt > 1) { can = true; break; }
				int te = *lower_bound(e, e+n, rd-e[j]), tf = *lower_bound(e, e+n, rd-e[i]);
				if(te+e[j] == rd || tf+e[i] == rd) continue;
				else { can = true; break; }
			}
			if(can) break;
		}
		if(i < 0) printf("no solution\n");
		else printf("%d\n", e[i]);
	}
	
	return 0;
}