Cod sursa(job #133243)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 7 februarie 2008 22:41:36
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 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");

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 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;
 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);
 intersort(1,n);
 //for (i=1; i<=n; i++)
 // fprintf(g,"%d ",a[i]);
 solve();
 return 0;
}