Cod sursa(job #422313)

Utilizator drywaterLazar Vlad drywater Data 22 martie 2010 15:08:31
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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,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++)
				l[nr++]=v[i]+v[j]+v[k];
	nr--;
	sort(l+1,l+nr+1);
	if (l[nr]<s/2)
		fprintf(g,"-1");
	else
	{
	for (i=0;l[i]<=s/2 && ok==0;i++)
	{
		if (l[i]*2==s)
		{
			ok=1;
			p1=p2=l[i];
		}
		else
		{
			st=i+1;
			dr=nr;
			while (st+1<dr)
			{
				mij=(st+dr)/2;
				if (l[mij]>s-l[i])
					dr=mij;
				else {if (l[mij]<s-l[i]) {if (st!=mij) st=mij; else st++;} else st=dr=mij;}
			}
			if (l[dr]==s-l[i])
			{
				ok=1;
				p1=l[i];
				p2=s-l[i];
			}
			if (l[st]==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 (p1==p2 && p2==-1) ok=1;
			}
	}
	}
	fclose(g);
	return 0;
}