Cod sursa(job #53485)

Utilizator Mishu91Andrei Misarca Mishu91 Data 22 aprilie 2007 12:34:04
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include<cstdio>
int a[110];
void intersc(int x,int y)
{
  int aux;
  aux=a[x];
  a[x]=a[y];
  a[y]=aux;     
}
int main()
{
  freopen("loto.in","r",stdin);
  freopen("loto.out","w",stdout);
  int n,s,v[110];
  scanf("%d %d",&n,&s);
  int i,j,k;
  for(i=1;i<=n;++i)
  {
    scanf("%d",&a[i]);
    j=i;
    while(j/2 && a[j/2]<a[j])
       {
       intersc(j/2,j);
       j/=2;   
       }
  }
  
  i=n;
  while(i)
  {
    intersc(1,i);
    i--;
 
    j=1;
    while(1) 
    {
      k=2*j;
      if(k>i) break;
      if(k+1<=i && a[k+1]>a[k]) k++;
      if(a[j] >= a[k]) break;
   
      intersc(j,k);
      j=k;       
    }        
  }
  while(a[n]>s) n--;
  int np=0;
  for(i=1;i<=n;i++) v[i]=a[n+1-i];
  int sum,i1,i2,i3,i4,i5,t,gast=0;
  int li,lf,m;
  lf=2; li=1;
  if(6*v[1]<s) {printf("-1"); return 0;}
  for(i1=1;i1<=n;++i1)
  {
    sum=v[i1];
    if(sum<s)
    for(i2=i1;i2<=n;++i2)
    {
      sum+=v[i2];
      if(sum<s);
      for(i3=i2;i3<=n;++i3)
      {
        sum+=v[i3];
        if(sum<s)    
        for(i4=i3;i4<=n;++i4)
        {
          sum+=v[i4];
          if(sum<s) 
          for(i5=i4;i5<=n;++i5)
          {
            sum+=v[i5];
            if(sum<s)
            t=s-sum;
            if(t>=v[n]&&t<=v[1])
            {
              li=1;
              lf=n;
              while(li<=lf)
              {
                m=(li+lf)/2;
                if(v[m]==t)break;
                else
                 if(v[m]>t)
                   li=m+1;
                   
                 else
                   lf=m-1;
              }
            
            if(li<=lf) {printf("%d %d %d %d %d %d",v[i1],v[i2],v[i3],v[i4],v[i5],v[m]);return 0;}
            }          
         sum-=a[i5];
          }
        sum-=a[i4];
        }
      sum-=a[i3];  
      }
    sum-=a[i2];
    }
  sum-=a[i1];
  }
  printf("-1");
  return 0;
}