Cod sursa(job #1022401)

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

void qksort(asociere v[],long st,long dr)
{long i=st,j=dr,piv;
    srand(time(0));
    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)
        {swap(v[i].val,v[j].val);
            swap(v[i].a,v[j].a);
            swap(v[i].b,v[j].b);
            swap(v[i].c,v[j].c);
            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(k=1;k<=nr&&gasit==0;k++)
    {aux=caut_binar(sum,k,nr,s-sum[k].val);
        if(aux!=-1)
        {gasit=1;g<<sum[k].a<<" "<<sum[k].b<<" "<<sum[k].c<<" "<<sum[aux].a<<" "<<sum[aux].b<<" "<<sum[aux].c;}
    }
    if(gasit==0)
        g<<-1;
    f.close();g.close();
    return 0;
}