Cod sursa(job #133233)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 7 februarie 2008 22:24:58
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <stdio.h>
#include <cstdlib>

int a[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");

long part(int st, int dr)
{
 int i=st,j=dr,s=-1,aux,cc,p;
 while (i<j)
   {
    //cc=dr-st+1;
    //p=st+ rand() % cc;
    //aux=a[st];
    //a[st]=a[p];
    //a[p]=aux;
    
    if (a[i]<a[j])
      {
       aux=a[i];
       a[i]=a[j];
       a[j]=aux;
      }
    if (s==1) i++;
         else j--;
   }
 return i;
}
void qsort(int st, int dr)
{
 long p;
 if (st<dr)
   {
    p=part(st,dr);
    qsort(st,p-1);
    qsort(p+1,dr);
   }
}
int find(int st, int dr, int vl)
{
 long mij;
 while (st<=dr)
   {
    mij=(st+dr)/2;
    if (a[mij]==vl) return mij;
      else
        if (a[mij]>vl) st=mij+1;
                  else dr=mij-1;
   }
}
void solve()
{
 long vl;
 int aux;
 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);
 //for (i=1; i<=n; i++)
 // fprintf(g,"%d ",a[i]);
 solve();
 return 0;
}