Cod sursa(job #1019652)

Utilizator Dayanna000Amegica Dayanna Dayanna000 Data 31 octombrie 2013 18:49:08
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
int as[1000000],a1[1000000],a2[1000000];
void qs(int stanga, int dreapta)
    {
       int i, j, piv, aux,x,y,z,mi,ma;
       i=stanga;
       j=dreapta;
       x=as[rand()%(j-i+1)+i];
       srand(time(0));
       y=as[rand()%(j-i+1)+i];
       srand(time(0));
       z=as[rand()%(j-i+1)+i];
       srand(time(0));
       if(x<=y && x<=z)
          mi=x;
       if(y<=x && y<=z)
          mi=y;
       if(z<=x && z<=y)
          mi=z;
       if(x>=y && x>=z)
          ma=x;
       if(y>=x && y>=z)
          ma=y;
       if(z>=x && z>=y)
          ma=z;
      piv=x+y+z-mi-ma;
      while(i<=j)
      {
       while(as[i]<piv)
          i++;
       while(as[j]>piv)
          j--;
        if(i<=j)
        {
           aux=as[i];
           as[i]=as[j];
           as[j]=aux;
           aux=a1[i];
           a1[i]=a1[j];
           a1[j]=aux;
           aux=a2[i];
           a2[i]=a2[j];
           a2[j]=aux;
           i++;
           j--;
         }
      }
    if(stanga<j)
       qs(stanga,j);
    if(i<dreapta)
       qs(i,dreapta);
    }
int cb(int x,int st,int dr)
  {
      int mij;
      while(st<=dr)
        {
            mij=st+(dr-st)/2;
            if(as[mij]==x)
              return mij;
            if(as[mij]>x)
              dr=mij-1;
              else
              st=mij+1;

        }
    return -1;
  }
main()
{
    int i,j,k,s,nr=0,n,a[101],ok,d;
    ifstream f("loto.in");
    ofstream g("loto.out");
    f>>n>>s;
    for(i=1;i<=n;i++)
      f>>a[i];
    for(i=1;i<=n;i++)
       for(j=i;j<=n;j++)
          for(k=j;k<=n;k++)
             {
                 nr++;
                 as[nr]=a[i]+a[j]+a[k];
                 a1[nr]=a[i];
                 a2[nr]=a[j];
             }
    qs(1,nr);
    i=1;
    ok=0;
    while(i<=nr && ok==0)
      {
          d=cb(s-as[i],1,nr);
          if(d!=-1)
            {
                g<<a1[i]<<"  "<<a2[i]<<"  "<<as[i]-a1[i]-a2[i]<<"  "<<a1[d]<<"  "<<a2[d]<<"  "<<as[d]-a1[d]-a2[d];
                ok=1;
            }
        i++;
      }
    if(ok==0)
      g<<"-1";
    f.close();
    g.close();
    return 0;
}