Cod sursa(job #388475)

Utilizator Teodor94Teodor Plop Teodor94 Data 30 ianuarie 2010 11:59:32
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=1<<7;
const int M=1<<20;

int a[N],n,sum[M],poz1,poz2,poz3,nr;

void afis(int x)
{
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++)
			for (int k=j;k<=n;k++)
				if (a[i]+a[j]+a[k]==x)
				{
					poz1=i;
					poz2=j;
					poz3=k;
					return;
				}
}

void suma()
{
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++)
			for (int k=j;k<=n;k++)
			{
				nr++;
				sum[nr]=a[i]+a[j]+a[k];
			}				
}

bool cautbin(int x)
{
	int i=0,pas=1<<19;
	for (;pas;pas>>=1)
		if (sum[i+pas]<=x && i+pas<=nr)
			i+=pas;
	if (sum[i]==x)
		return true;
	else
		return false;
}

int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	int s;
	scanf("%d%d",&n,&s);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	suma();
	sort(sum+1,sum+nr+1);
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++)
			for (int k=j;k<=n;k++)
			{
				int x=s-(a[i]+a[j]+a[k]);
				if (cautbin(x))
				{
					afis(x);
					printf("%d %d %d %d %d %d",a[i],a[j],a[k],a[poz1],a[poz2],a[poz3]);
					return 0;
				}
			}
	printf("-1");
	return 0;
}