Cod sursa(job #1016396)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 26 octombrie 2013 10:39:34
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

const int MAXN = 104, MAXC = MAXN*MAXN*MAXN;

int N, v[MAXN], S, C, poz;

struct bilet
{
    int suma, l1, l2, l3;
}
sol[MAXC];

inline bool cmp (bilet a, bilet b)
{
    return a.suma < b.suma;
}

inline bool caut_bin (int val, int st, int dr)
{
    if (st == dr && sol[st].suma == val)
    {
        poz = st;
        return true;
    }
    else if (st == dr)
        return false;

    int mid = (st + dr)/2;
    if (sol[mid].suma >= val)
        return (val, st, mid-1);
    else
        return (val, mid+1, dr);
}

int main ()
{
    int i, p = 0, j, k;
    bool ok = false;

    fin >> N >> S;
    C = N*N*N;
    for (i=0; i<N; ++i)
        fin >> v[i];

    for (i=0; i<N; ++i)
        for (j=0; j<N; ++j)
            for (k=0; k<N; ++k)
            {
                sol[p].suma = v[i] + v[j] + v[k];
                sol[p].l1 = i+1;
                sol[p].l2 = j+1;
                sol[p++].l3 = k+1;
            }
    sort (&sol[0], &sol[C], cmp);

    for (i=0; i<C; ++i)
    {
        j = caut_bin (sol[i].suma, 0, C-1);
        if (S == (sol[i].suma + sol[j].suma))
        {
            fout << sol[i].l1 << " " << sol[i].l2 << " " << sol[i].l3 << " " << sol[j].l1 << " " << sol[j].l2 << " " << sol[j].l3;
            ok = true;
            break;
        }
    }

    if ( !ok )
        fout << -1;

    fin.close ();
    fout.close ();

    return 0;
}