Cod sursa(job #495097)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 23 octombrie 2010 23:29:51
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct point {
	int a,b,z,t;
	point *leg;
};
point *h[500000];
int c,l,v[1025],nr,n1,x,s1,ok,s2,i,j,s;

void creare(int &n1) {
	int m,x;
	m=(c*c*c)/3;
    x=1;
    while(x<=m) x*=2;
    m=(x/2+x)/2;
	n1=m;
}

void insert(int x,int a1,int b1,int z1,int t1) {
	point *p;
	p=new point;
	p->a=a1;
	p->b=b1;
	p->z=z1;
	p->t=t1;
	p->leg=h[x];
	h[x]=p;
}

int cautare(point *p,int s2) {
	while (p!=NULL) {
		if (((p->a)+(p->b))==s2) {
			if (p->z!=i && p->z!=j && p->t!=i && p->t!=j) return 1;
			else p=p->leg;
		}
		else p=p->leg;
	}
	return 0;
}

int main () {
	freopen("oite.in","r",stdin);
	freopen("oite.out","w",stdout);
	scanf("%d%d",&c,&l);
	n1=0;
	creare(n1);
	for (i=1; i<=c; i++) scanf("%d",&v[i]);
	for (i=1; i<=c-1; i++)
		for (j=i+1; j<=c; j++) {
			s=v[i]+v[j];
			x=s%n1;
			if (s<=l) 
			insert(x,v[i],v[j],i,j);
		}
	nr=0;
	for (i=1; i<c; i++)
		for (j=i+1; j<=c; j++) {
			s1=v[i]+v[j];
			s2=l-s1;
			if (s2>=0 && s2<=l) {
			x=s2%n1;
			ok=0;
			ok=cautare(h[x],s2);
			if (ok) 
				nr++;
			}
		}
	printf("%d\n",nr/4);
	return 0;
}