Cod sursa(job #1465752)

Utilizator theep0Cruceru Radu theep0 Data 27 iulie 2015 22:40:10
Problema Loto Scor 85
Compilator c Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <stdio.h>
#include <stdlib.h>
 
#define MAXN 86969 
 
typedef struct _s {
    unsigned long v1, v2, v3, sum;
    struct _s *next;
} s;
 
s **sums;
 
unsigned int hash(unsigned int 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++) {
        ns = sums[i];
        while (ns != NULL) {
            if (S - ns->sum > 0) {
                h = hash(S - ns->sum);
                ns2 = sums[h];
                while (ns2 != 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;
                    }
                    ns2 = ns2->next;
                }
                if (k) break;
            }
            ns = ns->next;
        }
        if (k) break;
    }
    if (! k) {
        printf("-1\n");
    }
 
    fclose(fi);
    fclose(fo);
    return 0;
}