Cod sursa(job #474640)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 4 august 2010 15:00:17
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<algorithm>
using namespace std;
#define N_MAX 102

struct p
{
	int i,j,k,s;
	p()
	{
	}
	p(const int i,const int j,const int k,const int s)
	{
		this->i=i;
		this->j=j;
		this->k=k;
		this->s=s;
	}
	bool operator < (const p &other) const
	{
		return this->s<other.s;
	}
};

p a3[N_MAX*N_MAX*N_MAX];

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

	int a[N_MAX],n,i,j,k,S,s1,s2,s3,s,Len=0;

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

	for(i=1;i<=n;i++)
	{
		s1=a[i];
		for(j=1;j<=n;j++)
		{
			s2=s1+a[j];
			for(k=1;k<=n;k++)
			{
				s3=s2+a[k];
				if(s3>S)
					continue;
				a3[++Len]=p(a[i],a[j],a[k],s3);
			}
		}
	}
	
	sort(a3+1,a3+Len+1);

	int lg,step,cb;
	for(lg=1;lg<Len;(lg<<=1));

	for(i=1;i<=Len;i++)
	{
		s=S-a3[i].s;
		for(step=lg,cb=0;step;(step>>=1))
		{
			if(cb+step<=Len&&a3[cb+step].s<=s)
				cb+=step;
		}
		if(a3[cb].s==s)
		{
			printf("%d %d %d %d %d %d\n",a3[i].i,a3[i].j,a3[i].k,a3[cb].i,a3[cb].j,a3[cb].k);

			return 0;
		}
	}
	
	printf("-1\n");

	return 0;
}