Cod sursa(job #486502)

Utilizator SheepBOYFelix Liviu SheepBOY Data 21 septembrie 2010 20:43:29
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<stdio.h>
#include<stdlib.h>
//#include<conio.h>

const int MAXVALS=120;

struct Trip{
int a,b,c;
};

int sum,nr,n,nums[MAXVALS];
Trip base[10000000];

int TripCmp(const Trip x,const Trip y)
{
	if(x.a<y.a)
		return -1;
	if(x.a>y.a)
		return 1;
	if(x.a==y.a)
	{
		if(x.b<y.b)
			return -1;
		if(x.b>y.b)
			return 1;
		if(x.b==y.b)
		{
			if(x.c<y.c)
				return -1;
			if(x.c>y.c)
				return 1;
		}
	}
	return 0;
}
int cmp(const void *a, const void *b)
{
	Trip x,y;
	x=*(Trip *)a;
	y=*(Trip *)b;
	
	return TripCmp(x,y);
}

void GenerateTriplets();
int BinSearch()
{
	int rez,rez2,i,st,dr,mij;
	char found=0;
	
	for(i=0;i<nr;++i)
	{
		st=0;
		dr=nr-1;
		rez=sum-base[i].a-base[i].b-base[i].c;
		
		while(st<=dr)
		{
			mij=((st+dr)>>1);
			if( rez > (rez2=base[mij].a+base[mij].b+base[mij].c))
				st=mij+1;
			if(rez<rez2)
				dr=mij;
			if(rez == rez2)
			{
				found=1;
				break;
			}
		}
		if(found)
			break;
	}
	if(!found)
		printf("-1");
	else
		printf("%d %d %d %d %d %d",base[i].a,base[i].b,base[i].c,base[mij].a,base[mij].b,base[mij].c);
}

int main()
{
	int i;
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	
	scanf("%d%d",&n,&sum);
	for(i=0;i<n;++i)
		scanf("%d",nums+i);
	
	GenerateTriplets();
	
	qsort(base,nr,sizeof(base[0]),cmp);
	
	BinSearch();
	
	return 0;
}

void GenerateTriplets()
{
	int i,j,k;
	
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			for(k=0;k<n;++k)
			{
				base[nr].a=nums[i];
				base[nr].b=nums[j];
				base[nr++].c=nums[k];
			}
}