首页 > 代码库 > hdu 4334 Trouble
hdu 4334 Trouble
Trouble
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4375 Accepted Submission(s): 1297
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 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <string.h> 5 #include <set> 6 using namespace std; 7 #define ll long long 8 ll a[5][300],s1[90000],s2[90000],s3[90000],sn1,sn2,sn3; 9 int main()10 {11 int n,t,i,j,k;12 cin>>t;13 while(t--)14 {15 cin>>n;16 for(i=0; i<5; i++)17 for(j=0; j<n; j++)18 scanf("%I64d",&a[i][j]);19 sn1=sn2=sn3=0;20 for(i=0; i<n; i++)21 for(j=0; j<n; j++)22 s1[sn1++]=a[0][i]+a[1][j];23 for(i=0; i<n; i++)24 for(j=0; j<n; j++)25 s2[sn2++]=a[2][i]+a[3][j];26 for(i=0; i<n; i++)27 s3[sn3++]=-a[4][i];28 sort(s1,s1+sn1);29 sort(s2,s2+sn2);30 sort(s3,s3+sn3);31 int ok=0;32 for(i=0;!ok&&i<sn3;i++)33 {34 j=0,k=sn2-1;35 while(j<sn1&&k>=0)36 {37 if(s1[j]+s2[k]==s3[i])38 {39 ok=1;40 break;41 }42 while(j<sn1&&k>=0&&s1[j]+s2[k]>s3[i])k--;43 while(j<sn1&&k>=0&&s1[j]+s2[k]<s3[i])j++;44 }45 }46 if(ok)printf("Yes\n");47 else printf("No\n");48 }49 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。