Cod sursa(job #133218)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 7 februarie 2008 21:50:23
Problema Loto Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <stdio.h>

int a[110];
long s,su;
int n,i,j,k,l,m;

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;
 while (i<j)
   {
    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<s)
                  {
                   vl=s-su;
                   aux=find(1,n,vl);
                   if (a[aux]==vl)
                     {
                      fprintf(g,"%d %d %d %d %d %d",a[i],a[j],a[k],a[l],a[m],a[aux]);
                      return ;
                     }                     
                  }
                su=su-a[m];
               }
             su=su-a[l];
            }
          su=su-a[k];
         }
       su=su-a[j];
      }
    su=su-a[i];
   }
 fprintf(g,"%d",-1);
}
int main()
{
 fscanf(f,"%d %d",&n,&s);
 for (i=1; i<=n; i++)
   fscanf(f,"%d",&a[i]);
 qsort(1,n);
 solve();
 return 0;
}