Cod sursa(job #53414)

Utilizator Mishu91Andrei Misarca Mishu91 Data 21 aprilie 2007 23:29:32
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 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]; if(v[i]%2==0) np++;}
  if(np==n&&s%2) {printf("-1"); return 0;}
  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&&gast==0;++i1)
  {
    sum=v[i1];
    for(i2=1;i2<=n&gast==0;++i2)
    {
      sum=v[i1];
      if(sum>s) break;
      for(i3=1;i3<=n&&gast==0;++i3)
      {
        sum=v[i1]+v[i2];
        if(sum>s) break;    
        for(i4=1;i4<=n&&gast==0;++i4)
        {
          sum=v[i1]+v[i2]+v[i3];
          if(sum>s) break; 
          for(i5=1;i5<=n&&gast==0;++i5)
          {
            sum=v[i1]+v[i2]+v[i3]+v[i4];
            if(sum>s) break;
            sum+=v[i5];
            t=s-sum;
            if(t>=0)
            {
              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) {gast=1; printf("%d %d %d %d %d %d",v[m],v[i5],v[i4],v[i3],v[i2],v[i1]);}
            }          
          }
        }
      }
    }
  }
  if(gast==0) printf("-1");
  return 0;
}