Cod sursa(job #133254)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 7 februarie 2008 22:55:15
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <stdio.h>   
#include <cstdlib>   
  
int a[110],b[110];   
long s,su;   
int n,i,j,k,l,m,st,dr,mij;   
  
FILE*f=fopen("loto.in","r");   
FILE*g=fopen("loto.out","w");   
  
void intersort(int st, int dr)   
{   
 int mij,nr1,nr2,nr=0,i;   
 if (st<dr)   
   {   
    mij=(st+dr)/2;   
    intersort(st,mij);   
    intersort(mij+1,dr);   
    nr1=st; nr2=mij+1;   
    while (nr1<=mij && nr2<=dr)   
      if (a[nr1]>a[nr2]) b[++nr]=a[nr1++];   
                    else b[++nr]=a[nr2++];   
    while (nr1<=mij) b[++nr]=a[nr1++];   
    while (nr2<=dr) b[++nr]=a[nr2++];   
    for (i=st; i<=dr; i++) a[i]=b[i-st+1];   
   }   
}   
void solve()   
{   
 long vl;   
 for (i=1; i<=n; i++)   
   {   
    su+=a[i];   
    if (su+a[n]<=s)   
    for (j=i; j<=n; j++)   
      {   
       su+=a[j];   
       if (su+a[n]<=s)   
       for (k=j; k<=n; k++)   
         {   
          su+=a[k];   
          if (su+a[n]<=s)   
          for (l=k; l<=n; l++)   
            {   
             su+=a[l];   
             if (su+a[n]<=s)   
             for (m=l; m<=n; m++)   
               {   
                su+=a[m];   
                if (su+a[n]<=s&su+a[1]>=s)   
                  {   
                   vl=s-su;   
                   st=m; dr=n;   
                    while (st<=dr)   
                     {   
                      mij=(st+dr)/2;   
                      if (a[mij]==vl)    
                       {   
                        fprintf(g,"%d %d %d %d %d %d",a[i],a[j],a[k],a[l],a[m],a[mij]);   
                        return ;   
                        }   
                        else  
                          if (a[mij]>vl) st=mij+1;   
                                    else dr=mij-1;   
                     }                        
                  }   
                su=su-a[m];   
               }   
             su=su-a[l];   
            }   
          su=su-a[k];   
         }   
       su=su-a[j];   
      }   
    su=su-a[i];   
   }   
 fprintf(g,"-1");   
}   
int main()   
{   
 fscanf(f,"%d %d",&n,&s);   
 for (i=1; i<=n; i++)   
   fscanf(f,"%d",&a[i]);   
 //qsort(1,n);   
 intersort(1,n);   
 //for (i=1; i<=n; i++)   
 // fprintf(g,"%d ",a[i]);   
 solve();   
 return 0;   
}