Cod sursa(job #370811)

Utilizator Adela_BaciuAdela Baciu Adela_Baciu Data 2 decembrie 2009 12:31:44
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct s3
{int x,y,z,suma;};
s3 s[1000010];
int ss,ok,n,i,j,k,p,poz,a[110],v[10];
bool comp(const s3 &a,const s3 &b)
{
	return (a.suma<b.suma);
}
int cb(int x)
{
	int pas,i;
	pas=1<<20;
	for(i=0;pas;pas>>=1)
	{
		if(i+pas<=p&&s[i+pas].suma<=x)
			i+=pas;
	}
	if(s[i].suma!=x)
		return -1;
	return i;
}
int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%d",&n,&ss);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{
				s[++p].suma=a[i]+a[j]+a[k];
				s[p].x=a[i];
				s[p].y=a[j];
				s[p].z=a[k];
			}
	sort(s+1,s+p+1,comp);
	ok=0;
	for(i=1;i<=p;i++)
	{
		poz=cb(ss-s[i].suma);
		if(poz!=-1)
		{
			v[1]=s[i].x;
			v[2]=s[i].y;
			v[3]=s[i].z;
			v[4]=s[poz].x;
			v[5]=s[poz].y;
			v[6]=s[poz].z;
			ok=1;
			break;
		}
	}
	if(ok==0)
		printf("-1");
	else
	{
	sort(v+1,v+6+1);
	for(i=1;i<=6;i++)
		printf("%d ",v[i]);
	}
	return 0;
}