Pagini recente » Cod sursa (job #3155045) | Cod sursa (job #1840304) | Cod sursa (job #351065) | Cod sursa (job #1794832) | Cod sursa (job #39255)
Cod sursa(job #39255)
#include <stdio.h>
#include <math.h>
#define infile "oite.in"
#define outfile "oite.out"
#define CMAX 1025
#define HASH_MIC 512
#define HASH_MARE 262000
struct NOD_HASH{int val,count; NOD_HASH *adr;};
const double A=(sqrt(5)-1.)/2.;
FILE *fin,*fout;
int C,L;
int x[CMAX];
NOD_HASH *hash[HASH_MIC],*HASH[HASH_MARE];
int SOL=0;
void citire()
{
fin=fopen(infile,"r");
fscanf(fin,"%d %d",&C,&L);
for(int i=0;i<C;i++)
fscanf(fin,"%d",&x[i]);
fclose(fin);
}
inline int h1(int x)
{
return (int)floor(HASH_MIC*(A*x-floor(A*x)));
}
inline int h2(int x)
{
return (int)floor(HASH_MARE*(A*x-floor(A*x)));
}
void insert_hash(NOD_HASH *(&prim), int x)
{
NOD_HASH *b=prim;
while(b)
{
if(b->val==x)
{
b->count++;
return;
}
b=b->adr;
}
b=new NOD_HASH;
b->val=x;
b->count=1;
b->adr=prim;
prim=b;
}
int search_hash(NOD_HASH *prim, int x)
{
NOD_HASH *b=prim;
while(b)
{
if(b->val==x)
return b->count;
b=b->adr;
}
return 0;
}
void init()
{
int i,j;
for(i=0;i<HASH_MIC;i++)
hash[i]=NULL;
for(i=0;i<HASH_MARE;i++)
HASH[i]=NULL;
for(i=0;i<C;i++)
insert_hash(hash[h1(x[i])],x[i]);
for(i=0;i<C;i++)
for(j=i+1;j<C;j++)
insert_hash(HASH[h2(x[i]+x[j])],x[i]+x[j]);
}
void solve()
{
int i,j,aux;
for(i=0;i<C;i++)
for(j=i+1;j<C;j++)
{
aux=search_hash(HASH[h2(L-x[i]-x[j])],L-x[i]-x[j]);
SOL+=aux;
if(aux)
{
SOL=SOL-search_hash(hash[h1(L-2*x[i]-x[j])],L-2*x[i]-x[j])-search_hash(hash[h1(L-x[i]-2*x[j])],L-x[i]-2*x[j]);
if(x[i]==x[j])
SOL++;
if(L-x[i]-x[j] == x[i]+x[j])
SOL++;
}
}
}
int main()
{
citire();
init();
solve();
fout=fopen(outfile,"w");
fprintf(fout,"%d\n",SOL/6);
fclose(fout);
return 0;
}