Cod sursa(job #140244)

Utilizator hadesgamesTache Alexandru hadesgames Data 21 februarie 2008 16:18:53
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#include <stdlib.h>
struct ceva
{
	int v,v1,v2,v3;
};
ceva b[1000005];
int a[105],nr;
int compare( const void* a, const void* b )
{   
	ceva* arg1 = (ceva*) a;
	ceva* arg2 = (ceva*) b;
	if( arg1->v < arg2->v )
		return -1;
	else
		if( arg1->v == arg2->v )
			return 0;   
		else
			return 1; 
}  
int binary_search(int val)
{
    int i, step;
    for (step = 1; step < nr; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < nr && b[i + step].v <= val)
           i += step;
	if (b[i].v==val)
		return i;
	else 
		return -1;
}
int cauta(int x)
{
	int u=1,p=nr,m;
	while (u<p)
	{
		m=(u+p)/2;
		if (b[m].v==x)
			return m;
		if (b[m].v<x)
			u=m+1;
		if (b[m].v>=x)
			p=m-1;
	}
	if (b[u].v==x)
		return u;
	else
		return -1;
}
int main()
{
	FILE *in,*out;
	int n,s,i,j,j2,x;
	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]);
	}
	for (i=1;i<=n;i++)
		for (j=i;j<=n;j++)
			for (j2=j;j2<=n;j2++)
			{
				nr++;
				b[nr].v=a[i]+a[j]+a[j2];
				b[nr].v1=a[i];
				b[nr].v2=a[j];
				b[nr].v3=a[j2];
			}
	qsort(b+1,nr,sizeof(b[1]),compare);
	for (i=1;i<=nr;i++)
	{
		if (s-b[i].v<b[i-1].v)
			break;
		x=binary_search(s-b[i].v);
		if (x!=-1)
		{
			fprintf(out,"%d %d %d %d %d %d",b[i].v1,b[i].v2,b[i].v3,b[x].v1,b[x].v2,b[x].v3);
			fclose(in);
			fclose(out);
			return 0;
		}
	}
	fprintf(out,"-1\n");
	fclose(in);
	fclose(out);
	return 0;
		
}