Cod sursa(job #143891)

Utilizator andreisfrentSfrent Andrei andreisfrent Data 26 februarie 2008 22:13:06
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <stdlib.h>

#define limita_sp 10000
#define limita_v 101

struct suma_trei
{
	int s,x,y,z;
};

suma_trei sp[limita_sp];
int v[limita_v];

int compara(const void* a, const void* b)
{
	return (sp[*((int*)a)].s-sp[*((int*)b)].s);
}

int cauta_binar(int s_cautata, int li, int ls)
{
	int j;
	while(li<ls)
	{
		j=(li+ls)/2;
		if(sp[j].s==s_cautata) return j;
		if(sp[j].s>s_cautata) ls=j-1;
		else li=j+1;
	}
	return 0;
}

int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	int i,j,k;
	int n,s;
	scanf("%d %d",&n,&s);
	for(i=1;i<=n;i++) scanf("%d",&v[i]);
	fclose(stdin);
	int csp = 0; //contor de sume partiale
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=n;++j)
		{
			for(k=1;k<=n;++k)
			{
				++csp;
				sp[csp].x=v[i];
				sp[csp].y=v[j];
				sp[csp].z=v[k];
				sp[csp].s=v[i]+v[j]+v[k];
			}
		}
	}
	//am creat vectorul sp de structuri de sume partiale, cu csp componente
	qsort(sp+1,csp,sizeof(sp[0]),compara);
	int x;
	for(i=1;i<=csp;++i)
	{
		x=cauta_binar(s-sp[i].s,i+1,csp);
		if(x)
		{
			printf("%d %d %d %d %d %d",sp[i].x,sp[i].y,sp[i].z,sp[x].x,sp[x].y,sp[x].z);
			fclose(stdout);
			return 0;
		}
	}
	printf("-1");
	fclose(stdout);
	return 0;
}