Cod sursa(job #270235)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 3 martie 2009 20:35:16
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<stdio.h>
struct semiloto
	{
	long s,a,b,c;
	};
int n;
int suma,nr;
long a[102];
semiloto v[1000010];//v[1000000]


long partit(long st, long dr)
{
long i,j,m,piv;
semiloto a;
m=(st+dr)/2;
piv=v[m].s;
i=st-1;
j=dr+1;
while(1)
	{
	do{++i;}while(v[i].s<piv);
	do{--j;}while(v[j].s>piv);
	if(i<j)
		{
		a=v[i];
		v[i]=v[j];
		v[j]=a;
		}
	else
		return j;
	}
}

void quicks(long st, long dr)
{
long p;
if(st<dr)
	{
	p=partit(st,dr);
	quicks(st,p);
	quicks(p+1,dr);
	}
}


void read()
{
freopen("loto.in","r",stdin);
freopen("loto.out","w",stdout);
int i;
scanf("%d%ld",&n,&suma);
for(i=1;i<=n;i++)
	scanf("%ld",&a[i]);
int j,k;
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		for(k=1;k<=n;k++)
			{
			v[++nr].s=a[i]+a[j]+a[k];
			v[nr].a=a[i];
			v[nr].b=a[j];
			v[nr].c=a[k];
			}
quicks(1,nr);
}


void rez()
{
long i,x,st,dr,m;
for(i=1;i<=nr;i++)
	{
	x=suma-v[i].s;
	st=1;
	dr=nr;
	while(st<=dr)
		{
		m=(st+dr)>>1;
		if(v[m].s==x)
			break;
		if(v[m].s>x)
			dr=m-1;
		else
			st=m+1;
		}
	if(st<=dr)
		{
		printf("%ld %ld %ld %ld %ld %ld",v[i].a,v[i].b,v[i].c,v[m].a,v[m].b,v[m].c);
		return;
		}
	if(v[st].s==x)
		{
		printf("%ld %ld %ld %ld %ld %ld",v[i].a,v[i].b,v[i].c,v[st].a,v[st].b,v[st].c);
		return;
		}
	if(x==v[st-1].s)
		{
		printf("%ld %ld %ld %ld %ld %ld",v[i].a,v[i].b,v[i].c,v[st-1].a,v[st-1].b,v[st-1].c);
		return;
		}
	if(x==v[st+1].s)
		{
		printf("%ld %ld %ld %ld %ld %ld",v[i].a,v[i].b,v[i].c,v[st+1].a,v[st+1].b,v[st+1].c);
		return;
		}

	}
}


int main()
{
read();
rez();
return 0;
}