Cod sursa(job #165848)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 26 martie 2008 23:38:42
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<stdio.h>

int i,j,k,ok,mij;
long long nr,a[101],s,suma,l,r,sum[1000000],n;

void sort(int l,int r)
{int i,j,x,y;
	i=l;j=r;x=sum[(l+r)/2];
	do
	{
		while (sum[i]<x) i++;
		while (sum[j]>x) j--;
		if (i<=j)
		{
           y=sum[i];sum[i]=sum[j];sum[j]=y;           
           i++;j--;
        }
	}while (i<=j);
	if (l<j) sort(l,j);
	if (i<r) sort(i,r);
}
void afisare(long s1,long s2)
{int ok=1;
     for (i=1;i<=n && ok;i++)
         for (j=1;j<=n && ok;j++)
             for (k=1;k<=n && ok;k++)
                 if (a[i]+a[j]+a[k]==sum[s1])
                                             printf("%ld %ld %ld ", a[i], a[j], a[k]),ok=0;
     ok=1;
     for (i=1;i<=n && ok;i++)
         for (j=1;j<=n && ok;j++)
             for (k=1;k<=n && ok;k++)
                 if (a[i]+a[j]+a[k]==sum[s2])
                                             printf("%ld %ld %ld ", a[i], a[j], a[k]),ok=0;
}

int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%lld %lld",&n,&s);
	for(i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	nr=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				sum[++nr]=a[i]+a[j]+a[k];

	sort(1,nr);

	for (i=1;i<=nr;i++)
	{
		suma=s-sum[i];
		l=i;r=nr;
		while (l<r)
		{
			mij=(l+r)/2;
			if (sum[mij]==suma)
			   {
                 afisare(mij,i);
				 return 0;
			    }
			if (sum[mij]>suma) r=mij-1;
			else l=mij+1;
		}
	}
	printf("-1");
	return 0;
}