Cod sursa(job #112170)

Utilizator hadesgamesTache Alexandru hadesgames Data 3 decembrie 2007 16:49:32
Problema Loto Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>
struct ceva
{
	int v,a,b,c;
};
int a[102];
ceva b[1000000];

int compare( const void* a, const void* b ) {
    ceva *aa = (ceva*) a;
	ceva *bb = (ceva*) b;
    if( aa->v < bb->v ) return -1;
	if( aa->v > bb->v ) return 1;
	return 0;
 }
int main()
{
	FILE *in,*out;
	int n,s,i,j,nr,k,aux,p,u,m;
	in=fopen("loto.in","r");
	out=fopen("loto.out","w");
	fscanf(in,"%d%d",&n,&s);
	for (i=1;i<=n;i++)
		fscanf(in,"%d",&a[i]);
	nr=-1;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++)
			if (a[i]+a[j]+a[k]<=s)
			{
				nr++;
				b[nr].v=a[i]+a[j]+a[k];
				b[nr].a=a[i];
				b[nr].b=a[j];
				b[nr].c=a[k];
			}
	qsort(b,nr+1,sizeof(b[0]),compare);
	for (i=0;i<=nr;i++)
	{
		aux=s-b[i].v;
		p=0;
		u=nr;
		while (p<=u)
		{
			m=b[(u+p)/2].v;
			if (m==aux)
			{
				fprintf(out,"%d %d %d %d %d %d\n",b[i].a,b[i].b,b[i].c,b[(u+p)/2].a,b[(u+p)/2].b,b[(u+p)/2].c);
				fclose(in);
				fclose(out);
				return 0;
			}
			if (m<aux)
				p=(u+p)/2+1;
			if (m>aux)
				u=(u+p)/2-1;
		}
	}
	/*i=0;
	j=nr;
	while (i<j)
	{
		if (b[i].v+b[j].v==s)
		{
			fprintf(out,"%d %d %d %d %d %d\n",b[i].a,b[i].b,b[i].c,b[j].a,b[j].b,b[j].c);
			fclose(in);
			fclose(out);
			return 0;
		}
		if (b[i].v+b[j].v>s)
			j--;
		else
			i++;
	}
	if (b[i].v+b[j].v==s)
		{
			fprintf(out,"%d %d %d %d %d %d\n",b[i].a,b[i].b,b[i].c,b[j].a,b[j].b,b[j].c);
			fclose(in);
			fclose(out);
			return 0;
		}*/
	fprintf(out,"-1\n");
	fclose(in);
	fclose(out);
	return 0;
}