Cod sursa(job #2473)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 17 decembrie 2006 12:06:25
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
# include <stdio.h>

long int v[110];int n;long int s;

void quick (int li, int lf)
{
int i=li,j=lf,ii=0,jj=-1;long int aux;
while (i<j)
	{
	if (v[i]>v[j])
		{
		aux=v[i];v[i]=v[j];v[j]=aux;
		aux=ii;ii=-jj;jj=-aux;
		}
	i+=ii;j+=jj;
	}
if (i-li>1) quick(li,i-1);
if (lf-i>1) quick(i+1,lf);
}

void scrie(long int a, long int b, long int c, long int d, long int e, long int f)
{
FILE *g=fopen("loto.out","w");
if (a!=-1) fprintf(g,"%ld %ld %ld %ld %ld %ld\n",a,b,c,d,e,f);
else fprintf(g,"-1\n");
fclose(g);
}

int search()
{
int a,b,c,d,e,f;long int nra,nrb,nrc,nrd,nre,nrf;
for (a=1;a<=n;a++)
	for (b=a;b<=n;b++)
		{
		nrb=v[a]+v[b];
		c=b;
		while (v[c]+3*v[n]<s-nrb&&c<=n) c++;
		for (;c<=n&&nrb<s;c++)
			{
			nrc=nrb+v[c];
			d=c;
			while (v[d]+2*v[n]<s-nrc&&d<=n) d++;
			for (;d<=n&&nrc<s;d++)
				{
				nrd=nrc+v[d];
				e=d;
				while (v[e]+v[n]<s-nrd&&e<=n) e++;
				for (;e<=n&&nrd<s;e++)
					{
					nre=nrd+v[e];
					for (f=e;f<=n&&nre<s;f++)
						if (nre+v[f]==s) {scrie(v[a],v[b],v[c],v[d],v[e],v[f]);return 1;}
					}
				}
			}
		}
return 0;
}

int main()
{
int i;
FILE *f=fopen("loto.in","r");
fscanf(f,"%d%ld",&n,&s);
for (i=1;i<=n;i++) fscanf(f,"%ld",&v[i]);
quick(1,n);
fclose(f);
int ok=search();
if (ok==0) scrie(-1,0,0,0,0,0);
return 0;
}