Trouble
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2961 Accepted Submission(s): 893
Problem Description
Hassan is in trouble. His mathematics teacher has given him a very difficult problem called 5-sum. Please help him.
The 5-sum problem is defined as follows: Given 5 sets S_1,...,S_5 of n integer numbers each, is there a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0?
The 5-sum problem is defined as follows: Given 5 sets S_1,...,S_5 of n integer numbers each, is there a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0?
Input
First line of input contains a single integer N (1≤N≤50). N test-cases follow. First line of each test-case contains a single integer n (1<=n<=200). 5 lines follow each containing n integer numbers in range [-10^15, 1 0^15]. I-th line denotes set S_i for 1<=i<=5.
Output
For each test-case output "Yes" (without quotes) if there are a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0, otherwise output "No".
Sample Input
2 2 1 -1 1 -1 1 -1 1 -1 1 -1 3 1 2 3 -1 -2 -3 4 5 6 -1 3 2 -4 -10 -1
Sample Output
No Yes
1 //大致题意：判断五个数之和是否可能为0 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 typedef __int64 LL;//用define时出了错误 8 LL a[210]; 9 LL b[210]; 10 LL c[210]; 11 LL f[202*202]; 12 LL g[202*202]; 13 int num; 14 15 int main() 16 { 17 int i,j,k,T; 18 cin>>T; 19 while(T --) 20 { 21 cin>>num; 22 //memset(f, 0, sizeof f); 23 //memset(g, 0, sizeof g); 24 int cnt1 = 0; 25 int cnt2 = 0; 26 for(i = 0; i < num; i ++) 27 cin>>a[i]; 28 for(i = 0; i < num; i ++) 29 cin>>b[i]; 30 for(i = 0; i < num; i ++) 31 for(j = 0; j < num; j ++) 32 f[cnt1++] = a[i] + b[j]; 33 for(i = 0; i < num; i ++) 34 cin>>a[i]; 35 for(i = 0; i < num; i ++) 36 cin>>b[i]; 37 for(i = 0; i < num; i ++) 38 for(j = 0; j < num; j ++) 39 g[cnt2++] = a[i] + b[j]; 40 for(i = 0; i < num; i ++) 41 cin>>c[i]; 42 sort(f, f + cnt1); 43 sort(g, g + cnt2); 44 sort(c, c + num); 45 bool flag = 0; 46 for(i = 0; i < num; i ++) 47 { 48 LL temp = c[i]; 49 j = 0; 50 k = cnt2 - 1; 51 while(j < cnt1 && k >= 0) 52 { 53 if(f[j] + g[k] == (-temp)) 54 { 55 flag = 1; 56 break; 57 } 58 if(f[j] + g[k] <(-temp)) 59 j++; 60 else 61 k--; 62 } 63 } 64 if(flag) 65 cout<<"Yes"<<endl; 66 else 67 cout<<"No"<<endl; 68 } 69 return 0; 70 }
