Cod sursa(job #128546)

Utilizator katakunaCazacu Alexandru katakuna Data 27 ianuarie 2008 13:36:28
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<stdio.h>
int k2,aux,a,b,c,x,d,e,f,ok,p,u,mij,n,i,v[101],s[1000001],sx,i2,su,i3,k,h;

int main(){
FILE *f=fopen("loto.in","r");
fscanf(f,"%d %d",&n,&sx);
  for(i=1;i<=n;i++){
  fscanf(f,"%d",&v[i]);
  }

fclose(f);

  for(i=1;i<=n;i++){
    for(i2=1;i2<=n;i2++){
    su=v[i]+v[i2];
     for(i3=1;i3<=n;i3++){
     k++;
     s[k]=su+v[i3];
     }
    }
  }

k2=k;
//heap sort
  for(i=2;i<=k;i++){
  c=i;
  p=c>>1;

     while((p)&&(s[c]>s[p])){
     aux=s[c];
     s[c]=s[p];
     s[p]=aux;

     c=p;
     p=c>>1;

     }

  }


  for(i=k;i>1;i--){
  aux=s[i];
  s[i]=s[1];
  s[1]=aux;
  p=1;
  c=p<<1;

    k--;

      while(c<=k){
       if((s[c]<s[c+1])&&c<k){c++;}

       if(s[p]<s[c]){
       aux=s[p];
       s[p]=s[c];
       s[c]=aux;
       p=c;
       c=p<<1;
       }


       else{break;}

      }


  }




  for(i=1;i<=k2;i++){
  if(s[i]!=s[i-1]){
  su=sx-s[i];
    p=1;u=k2;

      while(p<=u){
      mij=(p+u)/2;

	if(s[mij]>=su){
	u=mij-1;
	}

	else{p=mij+1;}

      }

   if(s[p]==su){ok=1;break;}
  }
  }

FILE *g=fopen("loto.out","w");

 if(ok==1){
 sx=s[p];
 su=s[i];
 ok=0;
 k=0;

	    for(i=1;i<=n&&(!ok||!k);i++){
	for(i2=1;i2<=n&&(!ok||!k);i2++){
	x=v[i]+v[i2];
	  for(i3=1;i3<=n&&(!ok||!k);i3++){
	    if(x+v[i3]==su){ok=1;a=v[i];b=v[i2];c=v[i3];}
	    if(x+v[i3]==sx){k=1;d=v[i];e=v[i2];h=v[i3];}
	  }
	}
      }




 fprintf(g,"%d %d %d %d %d %d",a,b,c,d,e,h);

 }

 else{fprintf(g,"%d",-1);}

fclose(g);

return 0;
}