Cod sursa(job #1467500)

Utilizator horiainfoTurcuman Horia horiainfo Data 3 august 2015 15:08:30
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");

struct elem{int sum,poz;};
struct elem2{int conf[3],sum;};
int v[8],n,s,a[102],i,j,k,lgV;
vector<elem2> mat;
vector<elem> sume;

bool test(elem a,elem b)
{
    return a.sum<b.sum;
}

void afis(elem2 a,elem2 b)
{
    for(int i=0;i<3;i++)
        fout<<a.conf[i]<<' ';
    for(int i=0;i<3;i++)
        fout<<b.conf[i]<<' ';
}
int caut(int val)
{
    int mij,inc=0,sf=sume.size()-1;
    while(inc<=sf)
    {
        mij=(inc+sf)/2;
        if(sume[mij].sum==val)
            return mij;
        if(sume[mij].sum<val)
            inc=mij+1;
        else
            sf=mij-1;
    }
    return -1;
}
int main()
{
    fin>>n>>s;
    for(int i=1;i<=n;i++)
        fin>>a[i];

    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        for(j=i;a[i]+a[j]<=s && j<=n;j++)
            for(k=j;a[i]+a[j]+a[k]<=s && k<=n;k++)
            {
                elem2 aux;
                aux.sum = a[i]+a[j]+a[k];
                aux.conf[0] = a[i]; aux.conf[1] = a[j]; aux.conf[2] = a[k];
                mat.push_back(aux);
                elem aux2;
                aux2.poz = mat.size()-1;
                aux2.sum = a[i]+a[j]+a[k];
                sume.push_back(aux2);
            }
    sort(sume.begin(),sume.end(),test);
    for(int i=0;i<sume.size();i++)
    {
        int poz = caut(s-sume[i].sum);
        if(poz!=-1)
        {
            afis(mat[sume[i].poz],mat[sume[poz].poz]);
            return 0;
        }
    }
    fout<<-1;
    return 0;
}