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

Why WA?

Posted by pathfinder at 2007-10-05 14:25:37 on Problem 2549
#include <cstdio>
#include <algorithm>
int cmp(const void* p1,const void * p2)
{
	return *((long*)p1)-*((long*)p2);
}
long  s[1001];
int BinarySearch(const long A[], long key, int N);
int main()
{
	long n,i,j,k,tmp;
	bool flag;
	while(scanf("%d",&n) != EOF)
	{
		if(n == 0)
			break;
		for(i = 0;i < n; i++)
			scanf("%d",&s[i]);
		qsort((void*)&s[0],n,sizeof(s[0]),cmp);
		flag = false;
		for(i = n-1;i >= 3; i--)
		{
			for(j = i - 1;j >= 2; j--)
			{
				if((s[i] - s[j]) < s[0])
					continue;
				for(k = j - 1;k >= 1; k--)
				{
					tmp = s[i] - s[j] - s[k];
					if(BinarySearch(s,tmp,n) != -1)
					{
						flag = true;
						printf("%d\n",s[i]);
						//printf("%d = %d + %d + %d\n",s[i],s[j],s[k],tmp);
						//printf("%d   %d   %d   %d\n",i,j,k,BinarySearch(s,tmp,n));
						break;
					}
				}
				if(flag)
					break;
			}
			if(flag)
				break;
		}
		if(!flag)
			printf("no solution\n");
	}
	return 0;
}
int BinarySearch(const long A[], long key, int N)
{
	int Low, Mid, High;
	Low = 0;
	High = N - 1;
	while(Low <= High)
	{
		Mid = (Low + High) / 2; 
		if(A[Mid] < key)
			Low = Mid + 1;
		else if(A[Mid] > key)
			High = Mid - 1;
		else
			return Mid;
	}
	return -1;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator