Cod sursa(job #964303)

Utilizator poptibiPop Tiberiu poptibi Data 20 iunie 2013 16:02:52
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

#define Nmax 110
#define Mod 100021

vector<int> Hash[Mod];
int N, S, V[Nmax];

void Insert(int X)
{
    int K = abs(X) % Mod;
    for(vector<int> :: iterator it = Hash[K].begin(); it != Hash[K].end(); ++ it)
        if(*it == X)
            return ;
    Hash[K].push_back(X);
}

bool Is(int X)
{
    int K = abs(X) % Mod;
    for(vector<int> :: iterator it = Hash[K].begin(); it != Hash[K].end(); ++ it)
        if(*it == X)
            return 1;
    return 0;
}

void Reconstruct(int V1, int V2, int V3)
{
    int FinS = S - V1 - V2 - V3;
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= N; ++ j)
            for(int k = 1; k <= N; ++ k)
                if(V[i] + V[j] + V[k] == FinS)
                {
                    printf("%i %i %i %i %i %i\n", V1, V2, V3, V[i], V[j], V[k]);
                    exit(0);
                }
}

int main()
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);

    scanf("%i %i", &N, &S);
    for(int i = 1; i <= N; ++ i)
        scanf("%i", &V[i]);

    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= N; ++ j)
            for(int k = 1; k <= N; ++ k)
                Insert(V[i] + V[j] + V[k]);

    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= N; ++ j)
            for(int k = 1; k <= N; ++ k)
                if(Is(S - V[i] - V[j] - V[k]))
                    Reconstruct(V[i], V[j], V[k]);

    printf("-1");
    return 0;
}