Cod sursa(job #56654)

Utilizator cezar305Mr. Noname cezar305 Data 30 aprilie 2007 09:16:33
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream.h>
#include <iomanip.h>

fstream fin("loto.in",ios::in);
fstream fout("loto.out",ios::out);

long n,v[200],s,i,i1,i2,i3,i4,i5,i6,lmin,lmax,suma,nr=0,nrs;

long cauta(long x,long v[200]){
  long ls=0,ld=s+1,m;
  while (ld-ls>1){  
    m=(ls+ld)/2;
    if (m>=0) 
      if (v[m]==x) return 1;
      else if (v[m]<x) ld=m;
           else ls=m;
    else ld=ls;
  }      
  return 0;
}    

void qsort(long ii,long is){
  long i=ii,j=is,aux;
  while (i!=j){
    while ((v[i]<=v[j])&&(i!=j)) j--;
    if (i==j) break;
    aux=v[i];v[i]=v[j];v[j]=aux; i++;
    while ((v[i]<=v[j])&&(i!=j)) i++;  
    if (i==j) break;
    aux=v[i];v[i]=v[j];v[j]=aux;j--;    
  }       
  if (ii<i-1) qsort(ii,i-1);
  if (i+1<is) qsort(i+1,is);
}    

int main(){
  fin>>n>>s;
  for (i=1;i<=n;i++) fin>>v[i];
  qsort(1,n);
  if (6*v[1]>s || 6*v[n]<s) {fout<<-1;fin.close();fout.close();return 0;}
  lmin=1;lmax=n;
    while (5*v[n]+v[lmin]<s) lmin++;
    while (5*v[lmin]+v[lmax]>s) lmax--;
  for (i1=lmin;i1<=lmax;i1++){
    if (6*v[i1]>s) i1=lmax+1;
    else for (i2=i1;i2<=lmax;i2++){
      if (v[i1]+5*v[i2]>s) i2=lmax+1;
      else for (i3=i2;i3<=lmax;i3++){
        if (v[i1]+v[i2]+4*v[i3]>s) i3=lmax+1;
        else for (i4=i3;i4<=lmax;i4++){
          if (v[i1]+v[i2]+v[i3]+3*v[i4]>s) i4=lmax+1;
          else for (i5=i4;i5<=lmax;i5++){
            if (v[i1]+v[i2]+v[i3]+v[i4]+2*v[i5]>s) i5=lmax+1;  
            else { 
              nrs=s-(v[i1]+v[i2]+v[i3]+v[i4]+v[i5]);  
              if ((nrs>0) && cauta(nrs,v)){
                fout<<v[i1]<<" "<<v[i2]<<" "<<v[i3]<<" "<<
                v[i4]<<" "<<v[i5]<<" "<<nrs<<" ";
                fin.close();fout.close();return 0;
              }    
            }
  }}}}}    
  fout<<-1;
  fin.close();fout.close();        
return 0;
}