Cod sursa(job #456572)

Utilizator crushackPopescu Silviu crushack Data 16 mai 2010 03:56:49
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>
#define lung 100
#define lng 400000

int a[lung],per;

struct grupa
{int s,x,y,z;} s[lung*lung*lung];
bool bsearch(int,int,int);

int main()
{
	int n,su,i,j,k,nr,p;
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%d",&n,&su);
	for (i=0;i<n;i++)
		scanf("%d",&a[i]);
	nr=0;
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			for (k=0;k<n;k++)
			{
				s[nr].s=a[i]+a[j]+a[k];
				s[nr].x=a[i]; s[nr].y=a[j];  s[nr].z=a[k];
				nr++;
			}
	for (i=0;i<nr;i++)
	{
		p=i;
		for (j=i+1;j<nr;j++)
			if (s[j].s<s[p].s)
				p=j;
		if (p!=i)
		{
			grupa tmp=s[p];
			s[p]=s[i];
			s[i]=tmp;
		}
	}
	for (i=0;i<nr;i++)
		if ( bsearch(0,nr-1,su-s[i].s))
			break;
	if (i!=nr)
		printf("%d %d %d %d %d %d\n",s[i].x,s[i].y,s[i].z,s[per].x,s[per].y,s[per].z);
	else
		printf("-1\n");
	return 0;
}

bool bsearch(int ls,int ld,int x)
{
	int m;
	while (ls<ld)
	{
		m=(ls+ld)/2;
		if (s[m].s==x)
		{
			per=m;
			return true;
		}
		if (s[m].x>x)
			ls=m+1;
		else
			ld=m;
	}
	return false;
}