Cod sursa(job #221811)

Utilizator SheepBOYFelix Liviu SheepBOY Data 18 noiembrie 2008 09:52:38
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<stdio.h>
#include<stdlib.h>
#define N 1000007
int n,nn;
int s,tbl[101];
struct bilet{
	int x,y,z,s;
};
bilet v[N];
int comp(const void *a,const void *b)
{
	bilet aa=*(bilet *)a,bb=*(bilet *)b;
	if(aa.s>bb.s)
		return 1;
	if(aa.s<bb.s)
		return -1;
	return 0;
}
void scan()
{
	scanf("%d%d",&n,&s);
	for(int i=0;i<n;i++)
		scanf("%d",tbl+i);
}
void const_sum()
{
	int i,j,k;
	nn=0;
	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
			for(k=j;k<n;k++)
			{
				v[nn].x=tbl[i];
				v[nn].y=tbl[j];
				v[nn].z=tbl[k];
				v[nn].s=tbl[i]+tbl[j]+tbl[k];
				nn++;
			}
}

int caut(int x)
{
	int p=0,u=nn-1,m;
	while(p!=u)
	{
		m=(p+u)/2;
		if(x<=v[m].s)
			u=m;
		else
			p=m+1;
	}
	if(x==v[p].s)
		return p;
	return -1;
}

void solve()
{
	int i,p;
	for(i=0;i<nn;++i)
	{
		p=caut(s-v[i].s);
		if(p>=0)
		{
			printf("%d %d %d %d %d %d\n",v[i].x,v[i].y,v[i].z,v[p].x,v[p].y,v[p].z);
			return;
		}
	}
	printf("-1\n");
}

int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scan();	
	const_sum();
	qsort(v,nn,sizeof(v[0]),comp);
	solve();
	return 0;
}