Cod sursa(job #64725)

Utilizator FlorianFlorian Marcu Florian Data 5 iunie 2007 08:08:05
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<stdlib.h>
#include<stdio.h>
FILE*f=fopen("loto.in","r");
FILE*g=fopen("loto.out","w");
typedef struct
	{
	int b,i,j,k;
	}element;
element v[100002];
long n,p=0;
long s;
int c[100002];
void read()
	{
	long i;
	fscanf(f,"%ld %ld",&n,&s);
	for(i=0;i<n;++i) fscanf(f,"%ld",&c[i]);
	long j,k;
	for(i=0;i<n;++i)
		for(j=i;j<n;++j)
			for(k=j;k<n;++k)
			 {
			 v[p].b=c[i]+c[j]+c[k];
			 v[p].i=i; v[p].j=j; v[p].k=k;
			 p++;
			 }
	p--;
	}
int intcmp(const void *a, const void *b)
	{
	return *(int*)a-*(int*)b;
	}
long binary_search(long x, long k)
	{
	long j,i,m;
	i=k; j=p;
	while(i<=j)
		{
		m=(i+j)/2;
		if(v[m].b+x==s) return m;
		else if (v[m].b+x<s) i=m+1;
		else j=m-1;
		}
	return -2;
	}
void bug()
	{
	int i;
	fprintf(g,"\n");
	fprintf(g,"\n");
	for(i=0;i<=p;++i) fprintf(g,"%d ",v[i].b);
	 }
int calcul()
	{
	long i,ok=0,x;
	qsort(v,p,sizeof(v[0]),intcmp);
	for(i=0;i<=p;++i)
		{
		x=binary_search(v[i].b,i);
		if(x!=-2)
			{
			ok=1;
			fprintf(g,"%d %d %d %d %d %d",c[v[i].i],c[v[i].j],c[v[i].k],c[v[x].i],c[v[x].j],c[v[x].k]);
			return 0;
			}
		}
	fprintf(g,"-1");
	return 0;
	}
int main()
	{
	read();
	calcul();
	return 0;
	}