Cod sursa(job #69748)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 4 iulie 2007 08:53:52
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<stdio.h>
long int n,s,i,j,k,l,x[100],x3[1000000],pv[1000000],m,a,b,aux;
int swap(long int i1,long int i2);
int heapdown(long int ic,long int nc);
long int bsearch(long int ll,long int rr,long int vv);
int main()
{
	FILE *f,*g;
	f=fopen("loto.in","r");
	g=fopen("loto.out","w");
	fscanf(f,"%ld%ld",&n,&s);
	for(i=0;i<n;i++)
	fscanf(f,"%ld",&x[i]);
	for(i=0;i<n;i++)
	 for(j=0;j<n;j++)
	  for(k=0;k<n;k++)
	   { l=i+n*j+n*n*k;x3[l]=x[i]+x[j]+x[k];pv[l]=l;}
	m=n*n*n-1;
	for(i=m/2+2;i>=0;i--)
	heapdown(i,m);
	for(i=m;i>=0;i--)
	{ swap(0,i);heapdown(0,i-1);}
	a=-1;b=-1;
	for(i=0;i<=m;i++)
	{
	 if(x3[i]>s/2) break;
	 j=bsearch(i,m,s-x3[i]);
	 if(j){ a=pv[i];b=pv[j];break;}
	}
	if(a==-1) fprintf(g,"-1\n");
	else
	{ fprintf(g,"%ld ",x[a%n]);a/=n;
	  fprintf(g,"%ld ",x[a%n]);a/=n;
	  fprintf(g,"%ld ",x[a%n]);a/=n;
	  fprintf(g,"%ld ",x[b%n]);b/=n;
	  fprintf(g,"%ld ",x[b%n]);b/=n;
	  fprintf(g,"%ld ",x[b%n]);b/=n;
	}
	fprintf(g,"\n");
	fcloseall();
	return 0;
}
int swap(long int i1,long int i2)
{
	aux=x3[i1];x3[i1]=x3[i2];x3[i2]=aux;
	aux=pv[i1];pv[i1]=pv[i2];pv[i2]=aux;
	return 0;
}
int heapdown(long int ic,long int nc)
{
	long int is=2*ic+1,is1=2*ic+2;
	if(is>nc) return 0;
	if(is<nc) if(x3[is]<x3[is1]) is=is1;
	if(x3[ic]<x3[is]) {swap(ic,is); heapdown(is,nc);}
	return 0;
}
long int bsearch(long int ll,long int rr,long int vv)
{
	long int mm=(ll+rr)/2;
	if(ll>rr) return 0;
	if(vv<x3[ll]) return 0;
	if(vv>x3[rr]) return 0;
	if(x3[mm]==vv) return mm;
	if(vv<x3[mm]) return bsearch(ll,mm-1,vv);
	if(vv>x3[mm]) return bsearch(mm+1,rr,vv);
        return 0;
}