Cod sursa(job #201498)

Utilizator AndreyPAndrei Poenaru AndreyP Data 1 august 2008 08:18:46
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,s,sol1=-1,sol2,x1,x2,x3,x4,x5,x6;
int v[1000010];
int a[105];
bool caut(int x)
{
	int p=1,q=v[0],m;
	while(p<q)
	{
		m=(p+q)>>1;
		if(x<=v[m])
			q=m;
		else
			p=m+1;
	}
	if(v[p]==x)
		return true;
	return false;
}
int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	
	scanf("%d%d",&n,&s);
	int i,j,k,aux;
	bool caut1=true,caut2=true;
	for(i=1; i<=n; i++)
		scanf("%d",&a[i]);
	
	for(i=1; i<=n; i++)
	{
		for(j=i; j<=n; j++)
		{
			for(k=j; k<=n; k++)
			{
				v[++v[0]]=a[i]+a[j]+a[k];
				if(v[v[0]]>s)
					v[0]--;
			}
		}
	}
	
	sort(v+1,v+v[0]+1);
	
	for(i=1; i<=v[0] && sol1==-1; i++)
	{
		if(caut(s-v[i]))
		{
			sol1=v[i];
			sol2=s-v[i];
		}
	}
	
	if(sol1==-1)
	{
		printf("-1\n");
		return 0;
	}
	for(i=1; i<=n && (caut1 || caut2); i++)
	{
		for(j=i; j<=n && (caut1 || caut2); j++)
		{
			for(k=j; k<=n && (caut1 || caut2); k++)
			{
				aux=a[i]+a[j]+a[k];
				if(caut1)
				{
					if(sol1==aux)
					{
						caut1=false;
						x1=a[i];
						x2=a[j];
						x3=a[k];
					}
				}
				if(caut2)
				{
					if(sol2==aux)
					{
						caut2=false;
						x4=a[i];
						x5=a[j];
						x6=a[k];
					}
				}
			}
		}
	}
	
	printf("%d %d %d %d %d %d\n",x1,x2,x3,x4,x5,x6);
	return 0;
}