Cod sursa(job #283708)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 19 martie 2009 16:22:38
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<stdlib.h>
#define N 1000010
struct semiloto
{
	long s;
	long a,b,c;
};
long n,nr;
long suma;
long val[N];
long poz[N];
semiloto v[N];

void read()
{
	scanf("%ld%ld",&n,&suma);
	long i;
	for(i=1;i<=n;i++)
	{
		scanf("%ld",&val[i]);
	}
	long j,k;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{
				v[++nr].s=val[i]+val[j]+val[k];
				v[nr].a=val[i];
				v[nr].b=val[j];
				v[nr].c=val[k];
				poz[nr]=nr;
			}
}


int compar(const void *p, const void *q)
{
	long x=*(long *)p;
	long y=*(long *)q;
	if(v[x].s<v[y].s)
		return -1;
	if(v[x].s>v[y].s)
		return 1;
	return 0;
}

long cautare(long x)
{
	long st=1,dr=nr,mid;
	while(st!=dr)
	{
		mid=(st+dr)>>1;//pericol daca st+dr poate depasi long -> ((dr-st)>>1)+st
		if(x<=v[poz[mid]].s)
			dr=mid;
		else
			st=mid+1;
	}
	if(x==v[poz[st]].s)
		return st;
	return 0;
}

void solve()
{
	long i,p;
	for(i=1;i<=nr;i++)
	{
		p=cautare(suma-v[poz[i]].s);
		if(p)
		{
			printf("%ld %ld %ld %ld %ld %ld\n",v[poz[i]].a,v[poz[i]].b,v[poz[i]].c,v[p].a,v[p].b,v[p].c);
			return;
		}
	}
	printf("-1\n");
}

int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	read();
	qsort(poz+1,nr,sizeof(poz[0]),compar);
	solve();
	return 0;
}