Cod sursa(job #1190608)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 25 mai 2014 15:06:19
Problema Loto Scor 40
Compilator cpp Status done
Runda itmarathon Marime 1.57 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMax = 102, SMax = 600000000;

struct numar
{
    int value, i, j, k;
    numar() {value = i = j = k = 0;}
    numar(const int value, const int i, const int j, const int k)
    {
        this -> value = value;
        this -> i = i;
        this -> j = j;
        this -> k = k;
    }
    bool operator < (const numar & other) const
    {
        return value < other.value;
    }
};
int N, S;
int a[NMax];
numar v[NMax * NMax * NMax];
int nv;

int main()
{
    ifstream f ("loto.in");
    f >> N >> S;
    for (int i = 1; i <= N; ++ i)
        f >> a[i];
    f.close();
    for (int i = 1; i <= N; ++ i)
        for (int j = 1; j <= N; ++ j)
            for (int k = 1; k <= N; ++ k)
                v[++nv] = numar(a[i] + a[j] + a[k], i, j, k);
    sort(v+1, v+nv+1);
    for (int i = nv; i ; -- i)
    {
        int ns = S - v[i].value;
        int st = 1, dr = nv;
        while (st <= dr)
        {
            int mij = (st+dr) >> 1;
            if (v[mij].value == ns)
            {
                ofstream g("loto.out");
                g << a[v[i].i] << " " << a[v[i].j] << " " << a[v[i].k] <<" ";
                g << a[v[mij].i] << " " << a[v[mij].j] << " " << a[v[mij].k] << "\n";
                g.close();
                return 0;
            }
            else if (v[mij].value < ns)
                st = mij + 1;
            else
                dr = mij - 1;
        }
    }
    ofstream g("loto.out");
    g << "-1\n";
    g.close();
    return 0;
}