Description
Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.
Input
There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.
Output
For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO".
Sample Input
3 3 3 1 2 3 1 2 3 1 2 3 3 1 4 10
Sample Output
Case 1: NO YES NO
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 6 int a[505],b[505],c[505],d[500005]; 7 8 int main() 9 { 10 int l,m,n,s,q; 11 int i,j,k,cas=0; 12 while(scanf("%d %d %d",&l,&n,&m)!=EOF) 13 { 14 memset(d,0,sizeof(d)); 15 for(i=1;i<=l;i++) 16 scanf("%d",&a[i]); 17 for(i=1;i<=n;i++) 18 scanf("%d",&b[i]); 19 for(i=1;i<=m;i++) 20 scanf("%d",&c[i]); 21 scanf("%d",&s); 22 k=0; 23 for(i=1;i<=n;i++) 24 for(j=1;j<=m;j++) 25 d[++k]=b[i]+c[j]; 26 //sort(a+1,a+l+1); 27 sort(d+1,d+k+1); 28 d[k+1]=0; 29 30 printf("Case %d: ",++cas); 31 for(j=1;j<=s;j++) 32 { 33 int flg=0; 34 scanf("%d",&q); 35 for(i=1;i<=l;i++) 36 { 37 int p=q-a[i]; 38 int lb=1,ub=k; 39 while(lb<=ub) 40 { 41 int mid=(lb+ub)/2; 42 if(d[mid]==p) 43 { 44 flg=1; 45 break; 46 } 47 if(d[mid]<p) 48 lb=mid+1; 49 else 50 ub=mid-1; 51 } 52 if(flg==1) 53 break; 54 } 55 if(flg) 56 printf("YES "); 57 else 58 printf("NO "); 59 } 60 } 61 return 0; 62 }