Trouble

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3526    Accepted Submission(s): 1113

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

 

题意：

    给定五个集合，从五个集合中分别取出5个数，如果存在满足a1 +a2 + a3 + a4 +a5 = 0 

分析：

       事实上考虑如下问题，快速求解序列A，序列B中，是否有Ai+Bj=x ,记得是某知名公司的一道面试题吧；

 是两个指针的应用，将A，B升序排列，初试 i 指针指向A[1] ，j 指针指向 B[b_size] ,比较Ai + Bj 与 x 的

大小。若A[i]+B[j]<x , i 指针右移 ; 若 A[i]+B[j]>x , j 指针左移 。事实上是一个贪心的思想。

个人感悟：

     使用returen 比 break 好吧。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define Max(a,b) ((a)>(b)?(a):(b))using namespace std ;typedef long long LL ;struct Me{ LL N ,N_2 ,a_size ,b_size ,c_size; LL num[5][208] ; LL A[208*208] ; LL B[208*208] ; LL C[208] ; Me(){} Me(int n):N(n){} void read_init(){ for(int i=0;i<=4;i++) for(int j=1;j<=N;j++) scanf("%I64d",&num[i][j]) ; int k ; k=0; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) A[++k]=num[0][i]+num[1][j]; k=0 ; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) B[++k]=num[2][i]+num[3][j]; for(int i=1;i<=N;i++) C[i]=num[4][i] ; } int my_search(LL x){ int i=1 ; int j=b_size ; while(i<=a_size&&j>=1){ if(A[i]+B[j]
            
             x) j-- ; } return 0 ; } int calc(){ sort(A+1,A+1+N*N) ; a_size=unique(A+1,A+1+N*N)-(A+1) ; sort(B+1,B+1+N*N) ; b_size=unique(B+1,B+1+N*N)-(B+1) ; sort(C+1,C+1+N) ; c_size=unique(C+1,C+1+N)-(C+1) ; for(int i=1;i<=c_size;i++){ if(my_search(-1*C[i])) return 1 ; } return 0 ; } void gao_qi(){ read_init() ; if(calc()) puts("Yes") ; else puts("No") ; }};int main(){ int T ,N ; cin>>T ; while(T--){ scanf("%d",&N) ; Me me(N) ; me.gao_qi() ; } return 0 ;}