Cod sursa(job #133247)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 7 februarie 2008 22:44:54
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 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=su+a[i];
    if (su+a[n]<=s)
    for (j=i; j<=n; j++)
      {
       su=su+a[j];
       if (su+a[n]<=s)
       for (k=j; k<=n; k++)
         {
          su=su+a[k];
          if (su+a[n]<=s)
          for (l=k; l<=n; l++)
            {
             su=su+a[l];
             if (su+a[n]<=s)
             for (m=l; m<=n; m++)
               {
                su=su+a[m];
                if (su+a[n]<=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;
}