Cod sursa(job #582879)

Utilizator cumbaiaMihai Bercu cumbaia Data 16 aprilie 2011 14:27:00
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
#include<cstdlib>
#include<algorithm>

using namespace std;

int n,s,v[101],sol[7],ss[1<<20],nr;
bool stop;

void scrie(int start,int end)
{
	int i;
	for(i=start;i<=end;++i)
		printf("%d ",v[sol[i]]);
	if(end==6)
		exit(0);
}


void bkt(int p,int sum)
{
	int i;
	//scrie();
	if(p==4)
	{
		ss[++nr] = sum;
		return;
	}
	for(i=1;i<=n;++i)
	{
		sol[p] = i;
		bkt(p+1,sum+v[sol[p]]);
	}
}

void bkt2(int start,int end,int p,int sum)
{
	int i;
	if(stop)
		return;
	//scrie(start,p-1);
	if(p==1+end)
	{
		if(sum==0)
		{
			scrie(start,end);
			stop = true;
		}
		return;
	}
	for(i=1;i<=n;++i)
	{
		sol[p] = i;
		bkt2(start,end,p+1,sum-v[sol[p]]);
	}
}

int caut(int x)
{
	int i,pas=1<<19;
	for(i=0 ; pas ; pas>>=1)
		if(i+pas<=nr && ss[i+pas]<=x)
			i += pas;
	if(ss[i] != x)
		return 0;
	return i;
}

int main()
{
	int i,r;
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%d",&n,&s);
	for(i=1;i<=n;++i)
		scanf("%d",&v[i]);
	bkt(1,0);
	sort(ss+1,ss+nr+1);
	/*
	for(i=1 ; i<=nr ; i++)
		printf("%d ",ss[i]);
	printf("\n");
	*/
	for(i=1 ; i<=nr ; i++)
	{
		r = caut(s-ss[i]);
		if(r!=0)
		{
			//printf("pot obtine suma %d\n",ss[i]);
			stop=false;
			bkt2(1,3,1,ss[i]);
			stop=false;
			bkt2(4,6,4,s-ss[i]);
		}
	}
	printf("-1\n");
	return 0;
}