Description
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2 28 ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
Sample Output
5
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
#include<cstdio>
#include<string.h>
#include<algorithm>
#define MAXN 4400
using namespace std;
int A[MAXN],B[MAXN],C[MAXN],D[MAXN];
int S[MAXN*MAXN];
int lower_bound1(int low,int high,int num,int a[])
{
int mid;
while(low<high)
{
mid=low+(high-low)/;
if(a[mid]>=num) high=mid;
else low=mid+;
}
return low;
}
int upper_bound1(int low,int high,int num,int a[])
{
int mid;
while(low<high)
{
mid=low+(high-low)/;
if(a[mid]<=num) low=mid+;
else
high=mid;
}
return low;
}
int main()
{
int n,i;
int p;
int cout=;
int l,r,j;
while(scanf("%d",&n)!=EOF)
{
cout=;
for(i=;i<n;i++)
scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
p=;
for(i=;i<n;i++)
for(j=;j<n;j++)
S[p++]=A[i]+B[j];
sort(S,S+p);
for(i=;i<n;i++)
for(j=;j<n;j++)
{
int t=C[i]+D[j];
l=lower_bound1(,p,-t,S);
r=upper_bound1(,p,-t,S);
cout+=(r-l);
}
printf("%d\n",cout);
}
return ;
}