Cod sursa(job #804470)

Utilizator dariusdariusMarian Darius dariusdarius Data 29 octombrie 2012 20:51:18
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int sums[1000007],a[107],n,s,u;
inline bool bs(int val)
{
	int st=1,dr=u,med;
	while (st<=dr)
	{
		med=(st+dr)/2;
		if (sums[med]==val)
			return 1;
		if (sums[med]<val)
			st=med+1;
		else
			dr=med-1;
	}
	if (sums[med]==val)
		return 1;
	return 0;
}
int main()
{
	int ind,i,j,k;
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d %d",&n,&s);
	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++)
				sums[++u]=a[i]+a[j]+a[k];
	sort(sums+1,sums+u+1);
	for (ind=1;ind<=u;ind++)
		if (bs(s-sums[ind])==1)
		{
			bool ok=0;
			for (i=1;i<=n&&ok==0;i++)
				for (j=i;j<=n&&ok==0;j++)
					for (k=j;k<=n&&ok==0;k++)
						if (a[i]+a[j]+a[k]==sums[ind])
							printf("%d %d %d ",a[i],a[j],a[k]),ok=1;
			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-sums[ind])
						{
							printf("%d %d %d\n",a[i],a[j],a[k]);
							return 0;
						}
		}
	printf("-1\n");
	return 0;
}