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 (2362)

Posted by gemenhao at 2006-05-16 15:29:05 on Problem 2362
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define max 30

int ave, n, A[max],used[max],swap[max];
bool ok;
int cmp(const void *a , const void *b)
{
	return *(int * )b - *(int *)a;
}

void Search(int i, int now)
{
	if (now <= ave && ok && i < n )
	{
		if (now == ave)
		{
			ok = false;	return;
		}

		while (used[i] && i < n)
			i++;

		if (now + A[i] <= ave)
		{
			used[i] = 1;
			Search(i + 1,now + A[i]);
		}
		if ( ok )
		{
			used[i] = 0;
			Search(i + 1,now);
		}
	}
}

int main( )
{
	int t,i,sum;
	scanf("%d",&t);
	while ( t-- )
	{
		sum = 0;
		scanf("%d",&n);
		for (i = 0; i < n; i++)
		{
			scanf("%d",&A[i]);
			sum += A[i];
		}
		if (sum % 4 != 0)
		{
			printf("no\n");
			continue;
		}
		qsort(A,n,sizeof(A[0]),cmp);
		memset(swap,0,n*4);
		ave = sum / 4;
		ok = true;
		for (i = 0; i < 3; i++)
		{
			memcpy(used, swap, n*4);
			Search(i,0);
			if ( ok )
				break;
			else
				ok = true;
			memcpy(swap, used, n*4);
		}
		if (i < 3)
			printf("no\n");
		else
			printf("yes\n");
	}
	return 0;
}

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