Cod sursa(job #2380910)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 15 martie 2019 17:25:42
Problema Loto Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <vector>
using namespace std;

#define FILE_NAME "loto"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");

constexpr int HASH = 666013;
constexpr int MAX_DIM = 100 + 4;
struct ticket
{
    int sum;
    int x, y, z;
    ticket(int _x = 0, int _y = 0, int _z = 0)
    {
        x = _x, y = _y, z = _z;
        sum = x + y + z;
    }
};
vector < ticket > HashTable[HASH];
int Nums[MAX_DIM];
int N, S;

void addHash(ticket x)
{
    int hashed = x.sum % HASH;
    HashTable[hashed].push_back(x);
}

bool findHash(int sum, ticket &found)
{
    int hashed = sum % HASH;
    for(auto it : HashTable[hashed])
        if(it.sum == sum)
        {
            found = it;
            return true;
        }
    return false;
}

int main()
{
    in >> N >> S;
    for(int i = 0; i < N; ++i)
        in >> Nums[i];

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            for(int k = 0; k < N; ++k)
                addHash(ticket(Nums[i], Nums[j], Nums[k]));

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            for(int k = 0; k < N; ++k)
            {
                int sum = Nums[i] + Nums[j] + Nums[k];
                ticket sol;
                if(S - sum >= 0 && findHash(S - sum, sol))
                {
                    out << sol.x << ' ' << sol.y << ' ' << sol.z << ' '
                        << Nums[i] << ' ' << Nums[j] << ' ' << Nums[k] << '\n';

                    return 0;
                }
            }

    out << "-1\n";
    return 0;
}