Cod sursa(job #269870)

Utilizator ooctavTuchila Octavian ooctav Data 3 martie 2009 15:17:58
Problema Loto Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
// loto.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>
int e[104],suma;
int n;
int ep[7];

int f[1000001];

int compar(const void * a,const void * b)
{
	 return ( *(int*)a - *(int*)b );

}
void aranjare(int i,int mij,FILE *f2)
{
	int c=0,d=0;
	int l,j,k;
	for(j=1;j<=n;j++)
		for(k=1;k<=n;k++)
			for(l=1;l<=n;l++)
			{
				if(!c)
					if(e[j]+e[k]+e[l]==f[i])
					{
						c++;
						fprintf(f2,"%d %d %d ",e[j],e[k],e[l]);
					}
				if(!d)
					if(e[j]+e[k]+e[l]==f[mij])
					{
						c++;
						fprintf(f2,"%d %d %d ",e[j],e[l],e[k]);
					}
				if(c && d)
					break;
			}

}
void cautb(FILE *f2)
{
	int dr,st,mij,rez,b=0,j,i;
	for(i=1;i<=n*n*n;i++)
	{
		st=i;
		dr=n*n*n;
		while(st<=dr)
		{
			mij=st+(dr-st)/2;
			if(f[mij]+f[i]==suma)
			{
				aranjare(i,mij,f2);
				b=1;
				break;
			}
			else if(f[mij]+f[i]>suma)
					dr=mij-1;
			else
				st=mij+1;
		}
		if(b==1)
			break;
	}
	if(b==0)
		fprintf(f2,"-1");
}
void parsare(FILE *f1,int n)
{
	char c[1500];
	int nr=1,x=0,i;
	fgets(c,1200,f1);
	for(i=0;c[i]!=0;i++)
		if(c[i]==' ')
		{
			e[nr]=x;
			x=0;
			nr++;
		}
		else
			x=x*10+c[i]-'0';
	e[nr]=x;
}
int main()
{
	int i,j,l,k,o=1,p;

	FILE *f1,*f2;
	f1=fopen("loto.in","r");
	f2=fopen("loto.out","w");
	fscanf(f1,"%d %d\n",&n,&suma);
	parsare(f1,n);
	qsort(e,n,sizeof(int),compar);
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(l=1;l<=n;l++)
				f[o++]=e[i]+e[j]+e[l];
	qsort(f,n*n*n,sizeof(f[1]),compar);	
	cautb(f2);
	fclose(f1);
	fclose(f2);
	return 0;
}