HDU 4334 Trouble

原题传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4334

 

Trouble

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4387    Accepted Submission(s): 1302

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?

 

 

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

 

 

Source

 

2012 Multi-University Training Contest 4

 

 

 

Recommend

 

zhoujiaqi2010   |   We have carefully selected several similar problems for you:  4331 4332 4333 4335 4336

 

分析：前四个集合，两个两个一组合并，成两组p12,p34，，再分别对两个数组排序，然后用两个指针px指向p12的头部，py指向p34尾部，如果p12(px)+p34(py)==0-p5[i]，那么就Yes，如果是小于，则px++,如果是大于py--，一直到走完两个数组，则时间复杂度t*T（（n*2*log2N）*n）;

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN 210
int t,n,c,d,y,s;
long long temp;
long long p1[MAXN],p2[MAXN],p3[MAXN],p4[MAXN], p5[MAXN];
long long p12[MAXN*MAXN],p34[MAXN*MAXN];
bool flag;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        flag = false;
        scanf("%d",&n);
        c = 0;
        for(int i=0;i<n;i++){
                scanf("%I64d",p1+i);
        }
        for(int i=0;i<n;i++){
                scanf("%I64d",p2+i);
        }
        for(int i=0;i<n;i++){
                scanf("%I64d",p3+i);
        }
        for(int i=0;i<n;i++){
                scanf("%I64d",p4+i);
        }
        for(int i=0;i<n;i++){
                scanf("%I64d",p5+i);
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                p12[c++]=p1[i]+p2[j];
            }
        }
        d = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                p34[d++]=p3[i]+p4[j];
            }
        }
        sort(p12,p12+c);
        sort(p34,p34+d);
        for(int i=0;i<n;i++){
            s = 0;
            y = c-1;
            temp = 0-p5[i];
            while(s<c && y>=0){
                if(p12[s]+p34[y] == temp){
                        flag = true;
                        break;
                }
                if(p12[s]+p34[y]<temp){
                    s++;
                }
                else{
                    y--;
                }
            }
        }
        printf("%s\n",flag?"Yes":"No");
    }
    return 0;
}