Cod sursa(job #486503)

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

const int MAXVALS=120;

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

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

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

void GenerateTriplets();

int BinSearch()
{
	int rez,i,st,dr,mij;
	char found=0;
	
	for(i=0;i<nr;++i)
	{
		st=0;
		dr=nr-1;
		rez=sum-base[i].s;
		
		while(st<=dr)
		{
			mij=((st+dr)>>1);
			if( rez > base[mij].s)
				st=mij+1;
			if(rez<base[mij].s)
				dr=mij;
			if(rez == base[mij].s)
			{
				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];
				base[nr++].s=nums[i]+nums[j]+nums[k];
			}
}