Cod sursa(job #456579)

Utilizator crushackPopescu Silviu crushack Data 16 mai 2010 04:23:22
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <algorithm>
#define lung 100
#define lng 400000
using namespace std;

int a[lung],per,f[6];

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=i;j<n;j++)
			for (k=i;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=nr-1;i>=0;i--)
		if ( bsearch(0,nr-1,su-s[i].s))
			break;
	if (i!=nr)
	{
		f[0]=s[i].x;  f[1]=s[i].y;  f[2]=s[i].z  ; f[3]=s[per].x;  f[4]=s[per].y;  f[5]=s[per].z;
		sort(f,f+6);
		for (i=0;i<6;i++)
			printf("%d ",f[i]);
		printf("\n");
	}
	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)
			ld=m;
		else
			ls=m+1;
		if (ls==ld)
			break;
	}
	m=(ls+ld)/2;
	if (s[m].s==x)
	{
		per=m;
		return true;
	}
	return false;
}