Cod sursa(job #333924)

Utilizator rumburakrumburak rumburak Data 24 iulie 2009 17:09:20
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int N = (1<<7);
const int S = (1<<20);

int s,n,v[N],nr;
vector<int> sum;

void citire()
{
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]);
}

void sume()
{
	int i,j,k;
	for(i=1;i<=n;++i)
		for(j=i;j<=n;++j)
			for(k=j;k<=n;++k)
				sum.push_back(v[i]+v[j]+v[k]);
}

bool caut(int x)
{
	int n=sum.size(),i,pas;
	for(pas=1 ; pas<n ; pas<<=1);
	for(i=0 ; pas ; pas>>=1)
		if(i+pas<n && x>=sum[i+pas])
			i+=pas;
	return x==sum[i];
}

void scrie(int s)
{
	int i,j,k;
	for(i=1;i<=n;++i)
		for(j=i;j<=n;++j)
			for(k=j;k<=n;++k)
				if(v[i]+v[j]+v[k]==s)
					printf("%d %d %d\n",v[i],v[j],v[k]);
}

bool gasit()
{
	int i,j,k;
	for(i=1;i<=n;++i)
		for(j=i;j<=n;++j)
			for(k=j;k<=n;++k)
				if(caut(s-v[i]-v[j]-v[k]))
				{
					printf("%d %d %d ",v[i],v[j],v[k]);
					scrie(s-v[i]-v[j]-v[k]);
					return true;
				}
	return false;
}

int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	citire();
	sume();
	sort(sum.begin(),sum.end());
	if(!gasit())
		printf("-1\n");
	return 0;
}