Cod sursa(job #1465710)

Utilizator theep0Cruceru Radu theep0 Data 27 iulie 2015 21:54:26
Problema Lista lui Andrei Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 66683

typedef struct _s {
    unsigned long v1, v2, v3, sum;
    struct _s *next;
} s;

s **sums;

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x);

    return x % MAXN;
}

int main() {
    int i, j, k;
    int n, a[100];
    unsigned int h;
    FILE *fi, *fo;
    unsigned long S;
    s *ns, *ns2;

    sums = (s**)malloc(sizeof(s*) * MAXN);
    fi = freopen("loto.in", "r", stdin);
    fo = freopen("loto.out", "w", stdout);
    scanf("%d %lu", &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++) {
                h = hash(a[i] + a[j] + a[k]);
                ns = (s*) malloc(sizeof(s));
                ns->v1 = a[i];
                ns->v2 = a[j];
                ns->v3 = a[k];
                ns->sum = a[i] + a[j] + a[k];
                ns->next = sums[h];
                sums[h] = ns;
            }
        }
    }

    k = 0;
    for (i = 0; i < MAXN; i++) {
        while ((ns = sums[i]) != NULL) {
            h = hash(S - ns->sum);
            while ((ns2 = sums[h]) != NULL) {
                if (ns->sum + ns2->sum == S) {
                    printf("%lu %lu %lu %lu %lu %lu\n", ns->v1, ns->v2, ns->v3, ns2->v1, ns2->v2, ns2->v3);
                    k = 1;
                    break;
                }
            }
            if (k) break;
        }
        if (k) break;
    }
    if (! k) {
        printf("-1\n");
    }

    fclose(fi);
    fclose(fo);
    return 0;
}