Cod sursa(job #422403)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 22 martie 2010 17:30:45
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <algo.h>
FILE *f=fopen("loto.in","r"),*g=fopen("loto.out","w");
long long n,s,v[101],l[1000005],i,st,dr,j,k,nr,p1,p2,ok=0,mij;
int main(void)
{
	fscanf(f,"%lld%lld",&n,&s);
	for (i=1;i<=n;i++) fscanf(f,"%lld",&v[i]);
	for (i=1;i<=n;i++)
		for (j=i;j<=n;j++)
			for (k=j;k<=n;k++)
			{	if (v[i]+v[j]+v[k]<=s) {l[nr]=v[i]+v[j]+v[k]; nr++;}}
	nr--;
	sort(l+1,l+nr+1);
	for(j=1;j*2<=nr;j*=2);
	if (l[nr]<s/2)
		fprintf(g,"-1");
	else
	{
	for (i=0;i<=nr && ok==0;i++)
	{
		if (l[i]*2==s)
		{
			ok=1;
			p1=l[i];
			p2=l[i];
		}
		else
		{
			k=j;
			for (dr=0;k;k=k/2)
			{
				if (dr+k<=nr)
					{if (l[dr+k]<=s-l[i])
						dr=dr+k;}
			}
			if (l[dr]==s-l[i])
			{
				ok=1;
				p1=l[i];
				p2=s-l[i];
			}
		}
	}
	if (ok==0) fprintf(g,"-1");
	else
	{
	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 (v[i]+v[j]+v[k]==p1)
				{	fprintf(g,"%lld %lld %lld ",v[i],v[j],v[k]); p1=-1;}
				if (v[i]+v[j]+v[k]==p2)
				{	fprintf(g,"%lld %lld %lld ",v[i],v[j],v[k]); p2=-1;}
				if (p2==-1 && p1==-1) ok=1;
			}
	}
	}
	fclose(g);
	return 0;
}