Cod sursa(job #487198)

Utilizator stephy_yoyoIonescu Stefania stephy_yoyo Data 24 septembrie 2010 12:41:36
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
# include <cstdio>
# include <algorithm>

using namespace std;

struct suma
{
	long long s;
	char a,b,c;
};

suma su[1000000];
long long val[101],S;
int N,i,j,k,poz=0,v[6];

int cmp (suma x,suma y)
{
	return (x.s<y.s);
}

int cautbin (long long x)
{
	int min=1,max=poz;
	while (min<=max)
	{
		if (x==su[(min+max)/2].s)
			return (min+max)/2;
		else 
			if (x<su[(min+max)/2].s)
				max=(min+max)/2-1;
			else 
				min=( min+max)/2+1;
	}
	return 0;
}

int main ()
{
	freopen ("loto.in","r",stdin);
	freopen ("loto.out","w",stdout);
	scanf ("%d%lld",&N,&S);
	for (i=1;i<=N;i++)
		scanf ("%lld",&val[i]);
	for (i=1;i<=N;i++)
		for(j=i;j<=N;j++)
			for (k=j;k<=N;k++)
			{
				su[++poz].s=val[i]+val[j]+val[k];
				su[poz].a=i;
				su[poz].b=j;
				su[poz].c=k;
			}
	sort(su+1,su+poz+1,cmp);
	for (i=1;i<=poz;i++)
		if(k=cautbin(S-su[i].s))
		{
			v[0]=su[i].a;
			v[1]=su[i].b;
			v[2]=su[i].c;
			v[3]=su[k].a;
			v[4]=su[k].b;
			v[5]=su[k].c;
			sort(v,v+6);
			for (j=0;j<=5;j++)
				printf ("%d ",v[j]);
			return 0;
		}
	printf ("-1");
	return 0;
}