Cod sursa(job #1419112)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 14 aprilie 2015 18:45:35
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 101

using namespace std;

ifstream f("loto.in");
ofstream g("loto.out");

int i, j, k, n, s, nr;

vector <int> x;

struct loto
{
    int unu, doi, trei, val;
};

vector <loto> v;

bool cmp(loto a, loto b)
{
    return a.val<b.val;
}

int cautbin(int x)
{
    int st, dr, med;
    st=0;
    dr=v.size();

    while (st<=dr)
    {
        med=(st+dr)/2;
        if (v[med].val==x) return med;
        else
            if (x<v[med].val) dr=med-1;
        else
            if (x>v[med].val) st=med+1;
    }
    return -1;
}

int main()
{
    f>>n>>s;

    for (i=1; i<=n; ++i)
    {
        f>>nr;
        x.push_back(nr);
    }

    for (i=0; i<n; ++i)
        for (j=0; j<n; ++j)
        for (k=0; k<n; ++k)
        {
            loto alfa;
            alfa.val=x[i]+x[j]+x[k];
            alfa.unu=x[i];
            alfa.doi=x[j];
            alfa.trei=x[k];
            v.push_back(alfa);
        }

    sort(v.begin(), v.end(), cmp);

    n=v.size();
    bool gasit=0;

    for (i=0; i<=n; ++i)
    {
        int x=cautbin(s-v[i].val);
        if (x!=-1)
        {
            g<<v[i].unu<<" "<<v[i].doi<<" "<<v[i].trei<<" "<<v[x].unu<<" "<<v[x].doi<<" "<<v[x].trei<<'\n';
            gasit=1;
            return 0;
        }
    }

    if (!gasit) g<<"-1\n";

    return 0;
}