Cod sursa(job #53385)

Utilizator Mishu91Andrei Misarca Mishu91 Data 21 aprilie 2007 22:29:54
Problema Loto Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 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;
  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;       
    }        
  }
  int sum,i1,i2,i3,i4,i5,t,gast=0;
  int li,lf,m;
  for(i1=n;i1>0&&gast==0;--i1)
  {
    sum=a[i1];
    for(i2=n;i2>0&gast==0;--i2)
    {
      sum=a[i1];
      sum+=a[i2];
      for(i3=n;i3>0&&gast==0;--i3)
      {
        sum=a[i1]+a[i2];
        sum+=a[i3];
        for(i4=n;i4>0&&gast==0;--i4)
        {
          sum=a[i1]+a[i2]+a[i3]; 
          sum+=a[i4];
          for(i5=n;i5>0&&gast==0;--i5)
          {
            sum=a[i1]+a[i2]+a[i3]+a[i4]+a[i5];
            t=s-sum;
            if(t>0)
            {
              li=1;
              lf=n;
              while(li<=lf)
              {
                m=(li+lf)/2;
                if(a[m]==t)break;
                else
                 if(a[m]<t)
                   li=m+1;
                 else
                   lf=m-1;
              }
            }
            if(li<=lf) {gast=1; printf("%d %d %d %d %d %d",a[i1],a[i2],a[i3],a[i4],a[i5],a[m]);}
          }
        }
      }
    }
  }
  if(gast==0) printf("-1");
  return 0;
}