Cod sursa(job #443520)

Utilizator sliceskullcandySlice Skull Candy sliceskullcandy Data 17 aprilie 2010 12:14:16
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
//infoarena
//sliceskullcandy

#include <stdio.h>

long a[102],v[1000002],n,S,s,ok,nv,i,j,k;

void QuickSort(long L,long R)
{
	long i=L,j=R,aux,piv=v[(L+R)/2];

	while(i<=j)
	{
		while(v[i]<piv) i++;
		while(piv<v[j]) j--;
		if(i<=j)
		{
			aux=v[i];
			v[i]=v[j];
			v[j]=aux;
			i++;
			j--;
		}
	}

	if(L<j) QuickSort(L,j);
	if(i<R) QuickSort(i,R);
}

long BS(long x,long L,long R)
{
	long m;

	if(L<R)
	{
		m=(L+R)/2;
		if(x<v[m]) return BS(x,L,m);
		else
		if(x>v[m]) return BS(x,m+1,R);
		else
		return m;
	}
	else return -1;
}

void printout(long s)
{
	long i,j,k,stop;

	freopen("loto.out","w",stdout);

	stop=0;
	for(i=1;i<=n;i++)
	{
		for(j=i;j<=n;j++)
		{
			for(k=j;k<=n;k++)
				if(a[i]+a[j]+a[k]==s)
				{
					printf("%ld %ld %ld ",a[i],a[j],a[k]);
					stop=1;
					break;
				}
			if(stop) break;
		}
		if(stop) break;
	}

	stop=0;
	for(i=1;i<=n;i++)
	{
		for(j=i;j<=n;j++)
		{
			for(k=j;k<=n;k++)
				if(a[i]+a[j]+a[k]==S-s)
				{
					printf("%ld %ld %ld\n",a[i],a[j],a[k]);
					stop=1;
					break;
				}
			if(stop) break;
		}
		if(stop) break;
	}
}

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

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

	nv=0;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
				v[++nv]=a[i]+a[j]+a[k];

	QuickSort(1,nv);

	for(i=1;i<=nv;i++)
		if(v[i]<=S-v[i])
		{
			s=v[i];
			ok=BS(S-s,i,nv);
			if(ok!=-1)
			{
				printout(s);
				break;
			}
		}
		else break;

	if(ok==-1)
	{
		freopen("loto.out","w",stdout);
		printf("-1\n");
	}

	return 0;
}