Cod sursa(job #1463004)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 19 iulie 2015 16:30:41
Problema Loto Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <stdio.h>
#include <string.h>

#define MAX_N 100
#define MOD 666013
#define F(X) ((X) - (X) / MOD * MOD)
#define NIL -1
#define SOLSIZE 6

typedef struct {
  int v[3];
  int key;
  int next;
} cell;

cell l[MAX_N * MAX_N * MAX_N]; // buffer prealocat
int buffPtr;
int hash[MOD];                 // capete de liste alocate static

int v[MAX_N];                  // sirul dat
int sol[SOLSIZE];

static int inline hashFind(int key) {
  int i = hash[F(key)];

  while (i != NIL && l[i].key != key) {
    i = l[i].next;
  }
  return i;
}

static void inline addHash(int a, int b, int c) {
  int sum = a + b + c;
  int p = F(sum);

  l[buffPtr].key = sum;
  l[buffPtr].v[0] = a;
  l[buffPtr].v[1] = b;
  l[buffPtr].v[2] = c;
  l[buffPtr].next = hash[p];
  hash[p] = buffPtr;
  buffPtr++;
}

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

  fscanf(f, "%d%d", &n, &search);
  for (i = 0; i < n; i++) {
    fscanf(f, "%d", &v[i]);
  }
  fclose(f);

  memset(hash, NIL, sizeof(hash));

  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      for (k = 0; k < n; k++) {
        addHash(v[i], v[j], v[k]);
      }
    }
  }

  found = NIL;
  i = 0;

  while (i < n && found == NIL) {
    j = 0;
    while (j < n && found == NIL) {
      k = 0;
      while (k < n && found == NIL) {
        found = hashFind(search - (v[i] + v[j] + v[k]));
        k++;
      }
      j++;
    }
    i++;
  }

  f = fopen("loto.out", "w");
  if (found == NIL) {
    fputs_unlocked("-1\n", f);
  } else {
    sol[0] = v[i];
    sol[1] = v[j];
    sol[2] = v[k];
    sol[3] = l[found].v[0];
    sol[4] = l[found].v[1];
    sol[5] = l[found].v[2];
    for (i = 1; i < SOLSIZE; i++) {
      int x = sol[i];
      int j = i;
      while (j && sol[j - 1] > x) {
        sol[j] = sol[j - 1];
        j--;
      }
      sol[j] = x;
    }
    for (i = 0; i < SOLSIZE; i++) {
      fprintf(f, "%d ", sol[i]);
    }
    fputc_unlocked('\n', f);
  }
  fclose(f);
  return 0;
}