Cod sursa(job #53492)

Utilizator Mishu91Andrei Misarca Mishu91 Data 22 aprilie 2007 12:47:30
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 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,i6;
  int li,lf,m;
  //lf=2; li=1;
  //if(6*v[1]<s) {printf("-1"); return 0;}
  int q,p,sc=0;

for(i=1;i<=n;i++)
  {
  sc+=v[i];
  if(sc<s)
  for(j=i;j<=n;j++)
    {
    sc+=v[j];
    if(sc<s)
      for(k=j;k<=n;k++)
         {
         sc+=v[k];
         if(sc<s)
            for(q=k;q<=n;q++)
              {
              sc+=v[q];
              if(sc<s)
                 for(p=q;p<=n;p++)
                    {
                    sc+=v[p];
                    if(sc<s&&s-sc>=v[n]&&s-sc<=v[1])
                      {
                        int left=p,right=n;
                        int m=(left+right)/2;
                        int suma=s-sc;
                        while(v[m]!=suma&&left<=right)
                          {
                          if(suma<v[m])
                             left=m+1;
                          else right=m-1;
                          m=(left+right)/2;
                          }
                        if(v[m]==suma)
                          {
                          printf("%d %d %d %d %d %d",v[i],v[j],v[k],v[q],v[p],v[m]);
                          return 0;
                          }
                      }
                    sc-=a[p];
                    }
              sc-=a[q];
              }
         sc-=a[k];
         }
    sc-=a[j];
    }
  sc-=a[i];
  }
printf("%d",-1);
return 0;
}