Cod sursa(job #1368842)

Utilizator dragos_musanMusan Dragos dragos_musan Data 2 martie 2015 20:19:14
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<fstream>

using namespace std;

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

const int K = 666019, NMAX = 1000001;

int lst[K], val[K], urm[NMAX], n;
int v[NMAX];

void adauga(int x)
{
    int r = x % K;
    n++;
    val[n] = x;
    urm[n] = lst[r];
    lst[r] = n;
}

bool cauta(int x)
{
    int p = lst[x % K];
    while(p != 0)
    {
        if(val[p] == x)
            return 1;
        p = urm[p];
    }
    return 0;
}

void sterge(int x)
{
    int r = x%K;
    int p = lst[r];

    if(x == val[p])
    {
        lst[r] = urm[p];
        return;
    }
    while(urm[p] != 0)
    {
        if(val[urm[p]] == x)
        {
            urm[p] = urm[urm[p]];
            return;
        }
        p = urm[p];
    }
}

int main()
{
    int m,s ;

    f >> m >> s;

    for(int i = 1; i<=m; i++)
        f >> v[i];

    for(int i = 1; i<=m; i++)
        for(int j = 1; j<=m; j++)
            for(int k = 1; k<=m; k++)
                adauga(v[i] + v[j] + v[k]);

    bool ok = false;

    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=m; j++)
            for(int k = 1; k<=m; k++)
                if(cauta(s - (v[i] + v[j] + v[k])))
                {
                    g << v[i] << ' ' << v[j] << ' ' << v[k] << ' ';
                    for(int ii = 1; ii <= m; ii++)
                        for(int jj = 1; jj <= m; jj++)
                            for(int kk = 1; kk <= m; kk++)
                                if(v[ii] + v[jj] + v[kk] == s - (v[i] + v[j] + v[k]))
                                {
                                    g << v[ii] << ' ' << v[jj] << ' ' << v[kk] << ' ';
                                    ok = true;
                                    return 0;
                                }

                }
    if(!ok)
        g << -1 << '\n';
    return 0;
}