4 Values whose Sum is 0
Time Limit: 15000MS Memory Limit: 228000K
Total Submissions: 12654 Accepted: 3559
Case Time Limit: 5000MS
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 228 ) 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).
Source
Southwestern Europe 2005
輸入n 表示a b c d 四個集合都有n個元素 之後每行輸入4個集合中的一個元素 求這四個集合每個集合中拿出一個數 相加等於0的組數
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int a[4][4444],n; int num1[16100000],num2[16100000],c; int erfen(int left,int right,int k) { int i; while(left<=right) { int mid=(left+right)/2; int num=0; if(num2[mid]==k) { num=1; for(i=mid-1;i>=0&&num2[i]==k;i--) num++; for(i=mid+1;i<n*n&&num2[i]==k;i++) num++; return num; } else if(num2[mid]>k) right=mid-1; else left=mid+1; } return 0; } int main() { int i,j; while(scanf("%d",&n)!=EOF) { int num=0; c=0; for(i=0;i<n;i++) { scanf("%d %d %d %d",&a[0][i],&a[1][i],&a[2][i],&a[3][i]); } for(i=0;i<n;i++) for(j=0;j<n;j++) { num1[c]=a[2][i]+a[3][j]; num2[c++]=-(a[0][i]+a[1][j]); } sort(num2,num2+c); for(i=0;i<c;i++) { num+=erfen(0,n*n-1,num1[i]); } printf("%d\n",num); } return 0; }
#include <iostream> #include<stdio.h> using namespace std; #define MAX 1000000000 #define size 20345677 #define key 745 using namespace std; int n,a[4040],b[4040],c[4040],d[4040],ans; int hash[size],sum[size]; void Insert(int num) { int tmp=num; num=(num+MAX)%size; while(hash[num]!=MAX && hash[num]!=tmp) num=(num+key)%size; hash[num]=tmp; sum[num]++; } int Find(int num) { int tmp=num; num=(num+MAX)%size; while(hash[num]!=MAX && hash[num]!=tmp) num=(num+key)%size; if(hash[num]==MAX) return 0; else return sum[num]; } int main() { int i,j; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); for(i=0;i<size;i++) hash[i]=MAX; for(i=0;i<n;i++) for(j=0;j<n;j++) Insert(a[i]+b[j]); for(i=0;i<n;i++) for(j=0;j<n;j++) ans+=Find(-(c[i]+d[j])); printf("%d\n",ans); }