Cod sursa(job #129485)

Utilizator znakeuJurba Andrei znakeu Data 29 ianuarie 2008 16:25:03
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>
#include <stdlib.h>
struct thingy
{
	int x,y,z;
};

int cmp(const void *a, const void *b)
{
	thingy *aa=(thingy*)a, *bb=(thingy*)b;
	thingy k=*aa, l=*bb;
	int a1=k.x+k.y+k.z,a2=l.x+l.y+l.z;
	return a1-a2;
}

int main()
{
	int n,s,i,j,k,l,x1,x2,x3,sol=-1;
	int v[105];
	thingy v2[1000001];
	
	FILE *in  = fopen("loto.in","r");
	FILE *out = fopen("loto.out","w");
	
	fscanf(in,"%d%d",&n,&s);
	
	for (i=0; i<n; i++)
		fscanf(in,"%d",&v[i]);
	
	l=0;
	for (i=0; i<n; i++)
		for (j=i; j<n; j++)
			for (k=j; k<n; k++)
			{
				v2[l].x=v[i];
				v2[l].y=v[j];
				v2[l].z=v[k];
				l++;
			}
	
	qsort(v2,l,sizeof(v2[0]),cmp);
	
	for (i=0; i<l && sol!=1; i++)
	{
		x1=0;
		x2=l-1;
		x3=v2[i].x+v2[i].y+v2[i].z;
		while (x1<x2)
		{
			if (s-x3<v2[(x1+x2)/2].x+v2[(x1+x2)/2].y+v2[(x1+x2)/2].z)
				x2=(x1+x2)/2-1;
			else
			if (s-x3>v2[(x1+x2)/2].x+v2[(x1+x2)/2].y+v2[(x1+x2)/2].z)
				x1=(x1+x2)/2+1;
			else
			if (s-x3==v2[(x1+x2)/2].x+v2[(x1+x2)/2].y+v2[(x1+x2)/2].z)
				x1=(x1+x2)/2+1;
		}
		if (s-x3==v2[x1].x+v2[x1].y+v2[x1].z)
		{
			x2=i;
			i=l;
			sol=1;
		}
	}
	
	
	if (sol==1)
		fprintf(out,"%d %d %d %d %d %d\n",v2[x1].x,v2[x1].y,v2[x1].z,v2[x2].x,v2[x2].y,v2[x2].z);
	else
		fprintf(out,"-1\n");
	fclose(in);
	fclose(out);
	
	return 0;
}