Cod sursa(job #801937)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 25 octombrie 2012 14:42:41
Problema Loto Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct loto
{
	long long sum;
	long poz1,poz2,poz3;
};
loto b[1000007];
long a[107];
long n,s,u;
inline bool bs(long long val)//cautare binara
{
	long st=1,dr=u,med;
	while (st<=dr)
	{
		med=(st+dr)/2;
		if (b[med].sum==val)
			return 1;
		if (b[med].sum<val)
			st=med+1;
		else
			dr=med-1;
	}
	if (b[med].sum==val)
		return 1;
	return 0;
}
inline int cmp(loto a,loto b)
{
	return a.sum<b.sum;
}
int main()
{
	long i,j,k,i1,j1,k1;
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%ld %ld",&n,&s);
	for (i=1;i<=n;i++)
		scanf("%ld",&a[i]);
	//sume
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++)
				b[++u].sum=a[i]+a[j]+a[k],b[u].poz1=a[i],b[u].poz2=a[j],b[u].poz3=a[k];
	sort(b+1,b+u+1,cmp);//sortez
	bool ok=0;
	for(i=1;i<=u;i++)
		if (bs(s-b[i].sum)==1&&ok==0)
		{
			//afisez solutii
			for (i1=1;i1<=u;i1++)
				if (b[i1].sum==b[i].sum)
					{printf("%ld %ld %ld ",b[i1].poz1,b[i1].poz2,b[i1].poz3);break;}
			for (i1=1;i1<=u&&ok==0;i1++)
				if (b[i1].sum==s-b[i].sum)
					printf("%ld %ld %ld",b[i1].poz1,b[i1].poz2,b[i1].poz3),ok=1;
		}
	if (ok==0)
	printf("-1");
	return 0;
}