Cod sursa(job #2588999)

Utilizator StanCatalinStanCatalin StanCatalin Data 25 martie 2020 17:14:35
Problema Loto Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int dim = 1000005;
const int MOD = 666019;

int n,s,numere[dim];
int nr,lst[MOD],urm[dim],val[dim];

void Adauga(int suma)
{
    int c = suma%MOD;
    val[++nr] = suma;
    urm[nr] = lst[c];
    lst[c] = nr;
}

int Exista(int suma)
{
    int c = suma%MOD;
    for (int p=lst[c]; p!=0; p=urm[p])
    {
        if (val[p] == suma)
            return true;
    }
    return false;
}

int main()
{
    in >> n >> s;
    for (int i=1; i<=n; i++)
    {
        in >> numere[i];
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            for (int k=1; k<=n; k++)
            {
                Adauga(numere[i] + numere[j]+ numere[k]);
            }
        }
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            for (int k=1; k<=n; k++)
            {
                int care2 = Exista(s - numere[i] - numere[j] - numere[k]);
                if (care2)
                {
                    out << numere[i] << " " << numere[j] << " " << numere[k] << " ";
                    for (int i1=1; i1<=n; i1++)
                    {
                        for (int j1=1; j1<=n; j1++)
                        {
                            for (int k1=1; k1<=n; k1++)
                            {
                                if (numere[i1] + numere[j1]+ numere[k1] == s - numere[i] - numere[j] - numere[k])
                                {
                                    out << numere[i1] << " " << numere[j1] << " " << numere[k1] << " ";
                                    return 0;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    out << "-1";
    return 0;
}