Cod sursa(job #474632)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 4 august 2010 14:40:48
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<algorithm>
using namespace std;
#define N_MAX 102
int a[N_MAX];
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 Len;

int sol[7];

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

	int n,i,j,k,S;
	int s1,s2,s3,s;

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

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

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

	for(i=1;i<=n;i++)
	{
		s1=a[i];
		if(s1>S)
			break;
		for(j=1;j<=n;j++)
		{
			s2=s1+a[j];
			if(s2>S)
				break;
			for(k=1;k<=n;k++)
			{
				s3=s2+a[k];
				if(s3>S)
					break;
				s=S-s3;
				for(step=lg,cb=0;step;(step>>=1))
				{
					if(cb+step<=Len&&a3[cb+step].s<=s)
						cb+=step;
				}
				if(a3[cb].s==s)
				{
					sol[1]=a[i];
					sol[2]=a[j];
					sol[3]=a[k];
					sol[4]=a3[cb].i;
					sol[5]=a3[cb].j;
					sol[6]=a3[cb].k;
					sort(sol+1,sol+7);

					for(i=1;i<=6;i++)
						printf("%d ",sol[i]);

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

	return 0;
}