Pagini recente » Cod sursa (job #32091) | Cod sursa (job #2687400) | Cod sursa (job #195800) | Cod sursa (job #2357514) | Cod sursa (job #1765087)
#include <stdio.h>
#define nmax 1024
#define maxcomb ( ( ( 1 + nmax ) * nmax ) / 2 )
#define mod 702113
int v[nmax];
int hash[mod];
int val[maxcomb];
int next[maxcomb];
int frecv[maxcomb];
long long co;
int lung;
int caut( int s ){
int poz = hash[s%mod];
while( val[poz]!=s && poz!=0 )
poz = next[poz];
return poz;
}
void adauga( int s ){
int poz = caut( s );
if( poz!=0 )
frecv[poz]++;
else{
val[++lung] = s;
frecv[lung] = 1;
next[lung] = hash[ s%mod ];
hash[s%mod] = lung;
}
}
void oite( int s ){
co += frecv[ caut(s) ];
}
int main()
{
int n, s, i, j;
FILE *fin, *fout;
fin = fopen( "oite.in", "r" );
fscanf( fin, "%d%d", &n, &s );
for( i=0; i<n; i++ )
fscanf( fin, "%d", &v[i] );
fclose( fin );
for( i=0; i<n; i++ ){ ///inseram elementele in hash ca suma de 2 cate 2 => o(n^4) devine o(n^2)
for( j=i+1; j<n; j++ ){
if( s>v[i]+v[j] );
oite( s-v[i]-v[j] ); ///daca s - suma ultimelor 2 apare, insemana ca avem 4 oite distincte care au suma s
}
for( j=0; j<i; j++ ) ///adaugam suma primelor 2
adauga( v[i]+v[j] );
}
fout = fopen( "oite.out", "w" );
fprintf( fout, "%lld\n", co );
fclose( fout );
return 0;
}