Cod sursa(job #497483)

Utilizator Addy.Adrian Draghici Addy. Data 2 noiembrie 2010 17:11:21
Problema Oite Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>

const int MOD = 666013;
const int NMAX = 1048;

struct nod {
	int v, x, y;
	nod *next;
} *HASH[MOD];

int V[NMAX], A[MOD], n, x, i, j, k, a, b, c, nr;

int cauta (nod*, int);
void adauga (nod*&, int, int, int), sterge (nod*&, int, int, int);

int main () {
	
	freopen ("oite.in", "r", stdin);
	freopen ("oite.out", "w", stdout);
	
	scanf ("%d %d", &n, &x);
	
	for (i = 0; i < MOD; i++)
		HASH[MOD] = new nod;
	
	for (i = 1; i <= n; i++)
		scanf ("%d", &V[i]);
	
	for (i = 3; i < n; i++)
		for (j = i + 1; j <= n; j++) {
			a = V[i] + V[j], c = a % MOD;
			adauga (HASH[c], a, i, j); A[c]++;
		}
	
	for (k = 2; k < n - 1; k++) {
		for (i = 1; i < k; i++) {
			a = V[i] + V[k], b = x - a, c = b % MOD;
			if (A[c]) nr += cauta (HASH[c], b);
		}
		
		for (i = k + 2; i <= n; i++) {
			a = V[k+1] + V[i], c = a % MOD;
			sterge (HASH[c], a, k+1, i); A[c]--;
		}
	}
	
	printf ("%d", nr);
	
	return 0;
}

void adauga (nod *&H, int v, int x, int y) {
	
	nod *p;
	
	p = new nod;
	p -> v = v, p -> x = x, p -> y = y, p -> next = H;
	H = p;
}

int cauta (nod *H, int v) {
	
	nod *p;
	int nr = 0;
	
	for (p = H; p != NULL; p = p -> next)
		if (p -> v == v) {
			while (p != NULL && p -> v == v) {
				nr++;
				p = p -> next;
			}
			break;
		}
	
	return nr;
}

void sterge (nod *&H, int v, int x, int y) {
	
	nod *p, *aux;
	
	for (p = H; p != NULL; p = p -> next)
		if (p -> v == v && p -> x == x && p -> y == y) {
			if (p == H) {
				aux = H, H = H -> next;
				delete aux;
			}
			else {
				aux = p, p = p -> next;
				delete aux;
			}
			
			return;
		}
}