OJ Board

Code: Select all

/*
 * 10125 sumsets
 * submission 1 TLE
 * coded at 9:29am 26th dec 05
 *
 */


#include <stdio.h>

int main() {
	long a, b, c, d;
	long max_d;
	int n;
	long list[1000];

	while(scanf("%d",&n) && n) {
		max_d=-1;
		for(int i=0;i<n;i++) 
			scanf("%ld",&list[i]);
		//i am confused, can i omit those continue statement??
		for(a=0;a<n;a++) {
			for(b=0;b<n;b++) {
				if(a==b) continue;
				for(c=0;c<n;c++) {
					if(c==b || c==a) continue;
					for(d=0;d<n;d++) {
						if(d==a||d==b||d==c)   continue;
						if(list[a]+list[b]+list[c]==list[d])
							if(list[d]>max_d) max_d=list[d];
					}
				}
			}
		}
		
		if(max_d==-1) printf("no solution\n");
		else printf("%ld\n",max_d);
	}
return 0;
}

Code: Select all

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

Code: Select all

removed

Code: Select all

for(all a)
   for(all b)
      insert (a+b) at data structure
for(all d, starting from higher to lower)
   for(all c)
      if(d-c) is at the data structure...  :D 

Code: Select all

12
no solution
no solution
no solution
no solution
no solution                           all Output is correct ( after edit)
no solution
no solution
no solution
6
10
0

Code: Select all

#include <stdio.h>

void swap( int *a, int *b );
void bubble1( int n );
void bubble2( int n );
void search( int n1, int n2 );

int e[1000];
int a[500000];
int b[500000];
int x[500000];

int main( void )
{ 
	int number;
	int count;
	int i,j;
	
	while (1)
	{
		count=0;
		scanf( "%d", &number );
		if ( number == 0 )
			return 0;		
		while ( count < number )
		{
			scanf( "%d", &e[count] );
			count++;
		}
		
		bubble1( number );

		count=0;
		for( i=0; i<number; i++)
		{
			for( j=i+1; j<number; j++ )
			{
				a[count]=i;
				b[count]=j;
				x[count]=e[i]+e[j];
				count++;
			}
		}	
		bubble2( count );
		search( number, count );		
	}
}

void bubble1( int n )
{
	int i,j;

	for( i=0; i<=n-2; i++)
	{
		for( j=0; j<=n-i-2; j++ )
		{
			if( e[j]<e[j+1] )
				swap( &e[j], &e[j+1] );
		}
	}
}

void bubble2( int n )
{
	int i,j;

	for( i=0; i<=n-2; i++)
	{
		for( j=0; j<=n-i-2; j++ )
		{
			if( x[j]>x[j+1] )
			{
				swap( &x[j], &x[j+1] );
				swap( &a[j], &a[j+1] );
				swap( &b[j], &b[j+1] );
			}
		}
	}
}

void swap( int *a, int *b)
{
	int temp;
	
	temp=*a;
	*a=*b;
	*b= temp;
}

void search( int n1, int n2 )
{
	int ub,lb,m,key;
	int i,j,k;
	for( i=0; i<n1; i++ )
	{
		for( j=0; j<n1; j++ )
		{
			key=e[i]-e[j];
			lb=0;
			ub=n2-1;
			while( lb <= ub )
			{
				m=(lb+ub)/2;
				if( key<x[m] )
					ub=m-1;
				else if( key>x[m] )
					lb=m+1;
				else
				{
					if( !( (a[m]==b[m])||(a[m]==i)||(a[m]==j)||(b[m]==i)||(b[m]==j)||(i==j) ) )
					{
						printf("%d\n",e[i]);
						return;
					}
					k=m;
					while( key==x[k+1] && k+1<n1 )
					{
						k=k+1;
						if( !( (a[k]==b[k])||(a[k]==i)||(a[k]==j)||(b[k]==i)||(b[k]==j)||(i==j) ) )
						{
							printf("%d\n",e[i]);
							return;
						}
					}
					k=m;
					while( key==x[k-1] && k-1>=0 )
					{
						k=k-1;
						if( !( (a[k]==b[k])||(a[k]==i)||(a[k]==j)||(b[k]==i)||(b[k]==j)||(i==j) ) )
						{
							printf("%d\n",e[i]);
							return;
						}
					}
					break;
				}
			}
		}
	}
	printf("no solution\n");
}

Code: Select all

for(a=0;a<n;a++){
			for(b=0;b<n;b++){
				if(a==b)continue;
				for(c=0;c<n;c++){
					if(c==a || c==b)continue;
					for(d=0;d<n;d++){
						if(d==a || d==b || d==c)continue;
						if(num[a]+num[b]+num[c]==num[d])
							if(num[d]>max)max=num[d];
					}
				}
			}
		}
		if(max==0)printf("no solution\n");
		else printf("%d\n",max);