Cod sursa(job #2591651)

Utilizator AlexrotaruRotaru Alexandru Alexrotaru Data 30 martie 2020 21:39:56
Problema Loto Scor 45
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <stdlib.h>
#include <stdio.h>

#define MOD 666013
int v[101];

typedef struct triplet {
    char a, b, c;
} t_triplet;

typedef struct cell {
    t_triplet value;
    struct cell *next; 
} t_cell;

typedef struct list {
    t_cell *start, *end;
} t_list;

typedef t_list* t_hash;
typedef int (* f_hash) (int);

t_list *create_list();
int push_back_list(t_list **list, t_triplet value);
t_triplet *get_list(t_list *list, int sum);

int add_hash(t_hash *hash, f_hash f, t_triplet value);
t_triplet *get_hash(t_hash *hash, f_hash f, int sum);

t_list *create_list()
{
    t_list *list;

    list = (t_list *) malloc(sizeof(t_list));
    if(list == NULL) {
        return NULL;
    }
    list->start = list->end = NULL;
    return list;
}

int push_back_list(t_list **list, t_triplet value)
{
    t_cell *cell;

    if(*list == NULL) {
        *list = create_list();
        if(*list == NULL) {
            return -1;
        }
    }
    cell = (t_cell *) malloc(sizeof(t_cell));
    if(cell == NULL) {
        return -1;
    }

    cell->value.a = value.a;
    cell->value.b = value.b;
    cell->value.c = value.c;
    cell->next = NULL;
    if((*list)->end == NULL) {
        (*list)->start = (*list)->end = cell;
    }
    else {
        (*list)->end->next = cell;
        (*list)->end = cell;
    }
    return 0;
}

t_triplet *get_list(t_list *list, int sum) {
    if(list == NULL) {
        return NULL;
    }
    for(t_cell *cell = list->start; cell != NULL; cell = cell->next) {
        if(v[cell->value.a] + v[cell->value.b] + v[cell->value.c] == sum) {
            return &cell->value;
        }
    }
    return NULL;
}

int add_hash(t_hash *hash, f_hash f, t_triplet value) 
{
    int p;

    p = f(v[value.a] + v[value.b] + v[value.c]);
    return push_back_list(&(hash[p]), value);
}

t_triplet *get_hash(t_hash *hash, f_hash f, int sum)
{
    int p;

    p = f(sum);
    return get_list(hash[p], sum);
}

int modulo(int value)
{
    return value % MOD;
}

t_hash h[MOD];

int main()
{
    FILE *fin = fopen("loto.in", "r"),
         *fout = fopen("loto.out", "w");
    int n, s, i, j, k, found = 0;
    t_triplet value;
    t_triplet *res;

    fscanf(fin, "%d %d", &n, &s);
    for(i = 0; i < n; i++) {
        fscanf(fin,"%d", &v[i]);
    }
    for(i = 0; i < n; i++) {
        value.a = i;
        for(j = 0; j < n; j++) {
            value.b = j;
            for(k = 0; k < n; k++) {
                value.c = k;
                add_hash(h, &modulo, value);
            }
        }
    }
    for(i = 0; i < n && !found; i++) {
        for(j = 0; j < n && !found; j++) {
            for(k = 0; k < n && !found; k++) {
                if((res = get_hash(h, &modulo, s - (v[i] + v[j] + v[k])))) {
                    fprintf(fout, "%d %d %d %d %d %d",
                            v[i], v[j], v[k], v[res->a], v[res->b], v[res->c]);
                    found = 1;
                }
            }
        }
    }
    if(!found) {
        fprintf(fout, "-1");
    }

    fclose(fin);
    fclose(fout);
}