Cod sursa(job #1684747)

Utilizator EberardoVladianu Cosmin Eberardo Data 11 aprilie 2016 11:47:18
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct sum3
{
    int suma,poz1,poz2,poz3;
    sum3(int suma=0, int poz1=0, int poz2=0, int poz3=0):
        suma(suma),poz1(poz1),poz2(poz2),poz3(poz3) {}
};

bool cmp(sum3 x, sum3 y)
{
    return x.suma<y.suma;
}

int n,s,maxim=-1;
int dimensiune;

vector<sum3> a;
vector<int> v;

int binar(int pozi, int pozf, int val)
{
    int m;
    while(pozi<pozf)
    {
        m=(pozi+pozf)/2;
        if(a[m].suma>val)
            pozf=m-1;
        else
            pozi=m+1;
    }
    return pozi;
}

void citire()
{
    int i,j,k;
    fin>>n>>s;
    v.resize(n+2);

    for(i=1; i<=n; i++)
    {
        fin>>v[i];
        if(v[i]>maxim)
            maxim=v[i];
    }
    if(6*maxim>=s)
        for(i=1; i<=n; i++)
            for(j=i; j<=n; j++)
                for(k=j; k<=n; k++)
                {
                    a.push_back(sum3(v[i]+v[j]+v[k],i,j,k));
                }
    dimensiune=a.size()-1;
}

void afisare(int pozitie1, int pozitie2)
{
    fout<<v[a[pozitie1].poz1]<<' '<<v[a[pozitie1].poz2]<<' '<<v[a[pozitie1].poz3]<<' ';
    fout<<v[a[pozitie2].poz1]<<' '<<v[a[pozitie2].poz2]<<' '<<v[a[pozitie2].poz3];
}

void rez()
{
    int i;
    int de_cautat,poz;
    bool ok=false;
    if(6*maxim>=s)
    {
        sort(a.begin(),a.end(),cmp);
        for(i=dimensiune-1; 2*a[i].suma>=s; i--)
        {
            de_cautat=s-a[i].suma;
            poz=binar(0,dimensiune,de_cautat);
            if(a[poz].suma==de_cautat)
            {
                ok=true;
                afisare(i,poz);
                break;
            }
        }
    }
    if(ok==false)
        fout<<-1;
}

int main()
{
    citire();
    rez();
    return 0;
}