Cod sursa(job #1021102)

Utilizator vlad.florescu94FMI Florescu Vlad - Adrian vlad.florescu94 Data 3 noiembrie 2013 11:14:06
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
short n,i,j,k;
long s,v[101],nr=0,val,gasit=0,aux;
struct asociere
{
 short a,b,c;
 long val;
}sum[1000001];

void qksort(asociere v[],long st,long dr)
{long i=st,j=dr,piv,aux;
 piv=v[i+rand()%(j-i+1)].val;
 while(i<=j)
   {
    while(v[i].val<piv)
        i++;
    while(v[j].val>piv)
        j--;
    if(i<=j)
      {aux=v[i].val;v[i].val=v[j].val;v[j].val=aux;i++;j--;}
   }
 if(st<j)
    qksort(v,st,j);
 if(i<dr)
    qksort(v,i,dr);
}

long caut_binar(asociere a[],long st,long dr,long x)
{
 long m;
 bool ok=0;
 while(ok==0&&st<dr)
  {m=(st+dr)/2;
   if(a[m].val==x)
     ok=1;
   else
     if(a[m].val>x)
        dr=m-1;
      else
        st=m+1;
  }
 if(ok)
    return m;
 return -1;
}

int main()
{f>>n>>s;
 for(i=1;i<=n;i++)
    f>>v[i];
 for(i=1;i<=n;i++)
    for(j=i;j<=n;j++)
      for(k=j;k<=n;k++)
        {nr++;sum[nr].val=v[i]+v[j]+v[k];sum[nr].a=v[i];sum[nr].b=v[j];sum[nr].c=v[k];}
 qksort(sum,1,nr);
 for(i=1;i<=nr-1&&gasit==0&&sum[i].val<=s/2;i++)
   {aux=s-sum[i].val;
    if(caut_binar(sum,i,nr,aux)!=-1)
       {gasit=1;g<<sum[i].a<<" "<<sum[i].b<<" "<<sum[i].c<<" "<<sum[caut_binar(sum,i,nr,aux)].a<<" "<<sum[caut_binar(sum,i,nr,aux)].b<<" "<<sum[caut_binar(sum,i,nr,aux)].c;}
   }
 if(gasit==0)
    g<<-1;
 f.close();g.close();
 return 0;
}