Cod sursa(job #1514235)

Utilizator theprdvtheprdv theprdv Data 30 octombrie 2015 21:10:22
Problema Loto Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAXN 128
#define MOD 666013

struct hash_line
{
    short int no1, no2, no3;
    struct hash_line *link;
} *Hash[MOD];

int N, S, A[MAXN];

inline struct hash_line *find(int no1, int no2, int no3)
{
    int sum = A[no1] + A[no2] + A[no3], key, req = S - sum;
    struct hash_line *it;

    key = req % MOD;
    if (key < 0) key *= -1;

    for (it = Hash[key]; it; it = it->link)
        if (A[it->no1] + A[it->no2] + A[it->no3] == req)
            return it;

    key = sum % MOD;
    if (key < 0) key *= -1;

    struct hash_line *New = malloc(sizeof(struct hash_line));
    New->no1 = no1, New->no2 = no2, New->no3 = no3;
    New->link = Hash[key];
    Hash[key] = New;

    return  0;
}

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

    // local variables
    int i, j, k;
    struct hash_line *now;

    scanf("%d %d", &N, &S);
    for (i = 0; i < N; ++i) scanf("%d", &A[i]);


    for (i = 0; i < N; ++i)
        for (j = 0; j < N; ++j)
            for (k = 0; k < N; ++k)
            {
                now = find(i, j, k);
                if (!now) continue;

                printf("%d %d %d %d %d %d", A[i], A[j], A[k], A[now->no1], A[now->no2], A[now->no3]);
                return 0;
            }
    --N;
    now = find(N, N, N);
    !now ? printf("-1") : printf("%d %d %d %d %d %d", A[N], A[N], A[N], A[now->no1], A[now->no2], A[now->no3]);
    return 0;
}