Cod sursa(job #134289)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 11 februarie 2008 10:29:27
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<stdio.h>
long int n,s,i,x[102],j,k,p,s3[500002],c1[500002],c2[500002],c3[500002],l,r,ok,aux;
void hd(long int ic,long int nc);
void sh(long int i1,long int i2);
int main()
{
	FILE *f,*g;f=fopen("loto.in","r");g=fopen("loto.out","w");
	fscanf(f,"%ld%ld",&n,&s);
	for(i=1;i<=n;i++) fscanf(f,"%ld",&x[i]);
	for(i=1;i<=n;i++)
	 for(j=i;j<=n;j++)
	  for(k=j;k<=n;k++)
	   { p++;s3[p]=x[i]+x[j]+x[k];c1[p]=x[i];c2[p]=x[j];c3[p]=x[k];}
	for(i=p/2;i>=1;i--)hd(i,p);
	for(i=p;i>=1;i--){sh(1,i);hd(1,i-1);}
	l=1;r=p;
	for(l=1;l<=r;l++)
	{ while(s3[l]+s3[r]>s)r--;
	  if(s3[l]+s3[r]==s){ok=1;break;}
          while(s3[l]==s3[l+1])l++;
	}
	if(ok)
	{ fprintf(g,"%ld %ld %ld %ld %ld %ld\n",c1[l],c2[l],c3[l],c1[r],c2[r],c3[r]);
	  fcloseall();return 0;
	}
	fprintf(g,"-1\n");fcloseall();return 0;
}
void hd(long int ic,long int nc)
{
	long int is,is1;
	is=2*ic;is1=is+1;
	if(is>nc)return;
	if(is<nc) if(s3[is1]>s3[is])is=is1;
	if(s3[ic]<s3[is]){sh(is,ic);hd(is,nc);}
}
void sh(long int i1,long int i2)
{
	aux=s3[i1];s3[i1]=s3[i2];s3[i2]=aux;
	aux=c1[i1];c1[i1]=c1[i2];c1[i2]=aux;
	aux=c2[i1];c2[i1]=c2[i2];c2[i2]=aux;
	aux=c3[i1];c3[i1]=c3[i2];c3[i2]=aux;
}