Cod sursa(job #1579655)

Utilizator stoianmihailStoian Mihail stoianmihail Data 24 ianuarie 2016 22:17:55
Problema Oite Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>

#define MAX_MAP 523776
#define MOD 262144
#define Nadejde 1024

typedef struct {
  int v, freq, next;
} cell;

int N, S, count;
int val[Nadejde];

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

/** Cauta valoarea "x". **/
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 valoarea "x". **/
void insert(int x) {
  int pos = find(x);
  
  if (pos) {
    map[pos].freq++;
  } else {
    int h = x % MOD;
    map[++buff].v = x;
    map[buff].freq = 1;
    map[buff].next = hash[h];
    hash[h] = buff;
  }
}

/** Adauga la solutie numarul de aparitii al valorii "x". **/
void search(int x) {
  count += map[find(x)].freq;
}

int main(void) {
  int i, j;
  FILE *f = fopen("oite.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. */
  for (i = 0; i < N; i++) {
    for (j = i + 1; j < N; j++) {
      search(S - val[i] - val[j]);
    }
    for (j = 0; j < i; j++) {
      insert(val[i] + val[j]);
    }
  }

  /* Afisarea solutiei. */
  freopen("oite.out", "w", stdout);
  fprintf(stdout, "%d\n", count);
  fclose(stdout);

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