Cod sursa(job #446604)

Utilizator siminescuPaval Cristi Onisim siminescu Data 26 aprilie 2010 10:34:54
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#include<algorithm>
using namespace std;
long i,j,k,n,nv,A[102],v[1000002],ok,S;
long BS(long x,long L,long R)
{
	long m=(L+R)/2;
	if(L<R)
	{
		if(x<v[m]) return BS(x,L,m);
		else
		if(v[m]<x) return BS(x,m+1,R);
		else return 1;
	}
	else return 0;
}
void afisare(long sum)
{
	long i,j,k,ok;

	freopen("loto.out","w",stdout);

	ok=1;
	for(i=1;i<=n;i++)
	{
		for(j=i;j<=n;j++)
		{
			for(k=j;k<=n;k++)
				if(A[i]+A[j]+A[k]==sum)
				{
					ok=0;
					printf("%ld %ld %ld ",A[i],A[j],A[k]);
					break;
				}
			if(ok==0) break;
		}
		if(ok==0) break;
	}

	ok=1;
	for(i=1;i<=n;i++)
	{
		for(j=i;j<=n;j++)
		{
			for(k=j;k<=n;k++)
				if(A[i]+A[j]+A[k]==S-sum)
				{
					ok=0;
					printf("%ld %ld %ld\n",A[i],A[j],A[k]);
					break;
				}
			if(ok==0) break;
		}
		if(ok==0) break;
	}
}

int main()
{
	freopen("loto.in","r",stdin);

	scanf("%ld%ld",&n,&S);
	for(i=1;i<=n;i++)
		scanf("%ld",&A[i]);

	nv=0;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
				v[++nv]=A[i]+A[j]+A[k];

	sort(v+1,v+nv+1);

	ok=0;
	v[++nv]=S;
	for(i=1;i<=nv;i++)
		if(v[i]<=S-v[i])
		{
			ok=BS(S-v[i],i,nv);
			if(ok==1)
			{
				afisare(v[i]);
				return 0;
			}
		}
		else
		{
			freopen("loto.out","w",stdout);
			printf("-1\n");
			return 0;
		}

	return 0;
}