Cod sursa(job #159433)

Utilizator rethosPaicu Alexandru rethos Data 14 martie 2008 09:42:17
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream.h>
#define XM 1000001//100^3
#define NM 101
ofstream g("loto.out");
ifstream f("loto.in");
long v[NM],x[XM],p[XM];
long n,s,nrx;
void swap(long a,long b)
{long aux=x[a];
 x[a]=x[b];
 x[b]=aux;
}
void intercl(long st,long dr)
{long mij=(st+dr)/2;
 long i=st,j=mij+1,k=1;
 while(i<=mij&&j<=dr)
   {if(x[i]<x[j]) p[k]=x[i++];
    	else p[k]=x[j++];
    k++;
   }
 for (;i<=mij;i++,k++) p[k]=x[i];
 for (;j<=dr;j++,k++)  p[k]=x[j];
 for (i=1;i<=k-1;i++) x[st+i-1]=p[i];
}
void msort(long st,long dr)
{if(st>=dr) return;
 long mij=(st+dr)/2;
 msort(st,mij);
 msort(mij+1,dr);
 intercl(st,dr);
}
void afis(long a)
{int i,j,k;
 for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
       for (k=1;k<=n;k++)
          if(v[i]+v[j]+v[k]==a)
            {g<<v[i]<<' '<<v[j]<<' '<<v[k];
             return;
            }
}
int main()
{
 int i,j,k;
 f>>n>>s;
 for (i=1;i<=n;i++) f>>v[i];
 f.close();
 for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
       for (k=1;k<=n;k++)
          {nrx++;
           x[nrx]=v[i]+v[j]+v[k];
          }
 msort(1,nrx);
 long st=1,dr=nrx;
 while (st<=dr)
   {if(x[st]+x[dr]==s)
     {afis(x[st]);
      g<<' ';
      afis(x[dr]);
      g.close();
      return 0;
     }
    while (x[st]+x[dr]<s&&st<=nrx) st++;
    while (x[st]+x[dr]>s&&dr>=1) dr--;
   }
 g<<-1;
 g.close();
 return 0;
}