Cod sursa(job #39255)

Utilizator stef2nStefan Istrate stef2n Data 26 martie 2007 16:09:09
Problema Oite Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#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;
}