Cod sursa(job #1579458)

Utilizator stoianmihailStoian Mihail stoianmihail Data 24 ianuarie 2016 19:21:18
Problema Loto Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MOD 1048576
#define MAX_MAP 1000000
#define Nadejde 100

typedef struct {
  int i, j, k, v, next;
} cell;

int N, S;
int val[Nadejde];

/** Reprezentarea tabelei hash. **/
int buff;
int hash[MOD];
cell map[MAX_MAP + 1];

/** Construieste structura {i, j, k, v, next}. **/
cell make(int i, int j, int k, int v, int next) {
  cell tmp;
  tmp.i = i;
  tmp.j = j;
  tmp.k = k;
  tmp.v = v;
  tmp.next = next;
  return tmp;
}

/** Cauta valoarea "x" in tabela hash. **/
int find(int x) {
  if (x < 0) {
    return 0;
  }

  int pos, h = x % MOD;

  for (pos = hash[h]; (pos != 0) && (map[pos].v != x); pos = map[pos].next);
  return pos;
}

/** Adauga in tabela valoarea "x". **/
void insert(int x, int i, int j, int k) {
  if (!find(x)) {
    int h = x % MOD;
    map[++buff] = make(i, j, k, x, hash[h]);
    hash[h] = buff;
  }
}

int main(void) {
  int i, j, k, sum, pos;
  FILE *f = fopen("loto.in", "r");

  /* Citirea datelor. */
  fscanf(f, "%d %d", &N, &S);
  for (i = 0; i < N; i++) {
    fscanf(f, "%d", &val[i]);
  }
  fclose(f);

  /* Calcularea solutiei. */
  freopen("loto.out", "w", stdout);
  for (i = 0; i < N; i++) {
    for (j = i; j < N; j++) {
      for (k = j; k < N; k++) {
        sum = val[i] + val[j] + val[k];
        insert(sum, i, j, k);
        pos = find(S - sum);
        if (pos) {
          fprintf(stdout, "%d %d %d %d %d %d\n", val[map[pos].i], val[map[pos].j], val[map[pos].k], val[i], val[j], val[k]);
          exit(0);
        }
      }
    }
  }

  /* Daca nu am gasit nimic. */
  //assert(0);
  fprintf(stdout, "-1\n");
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}