O

O - Can you find it?

Time Limit:3000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u

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

Sample Output

Case 1:

YES

//很简单的题目

运用二分的思想去查找 a 和 b 组合的数组，是否有等于要求的

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 int a[505];
 7 int b[505];
 8 int c[505];
 9 int sum[505*505];
10 int x,y,z,num;//数组a，b，c的元素个数
11 
12 int find(int x)
13 {
14     int l=0,r=num-1;
15     int mid;
16     while (l<=r)
17     {
18         mid=(l+r)/2;
19         if (sum[mid]==x) return 1;
20         if (sum[mid]>x) r=mid-1;
21         if (sum[mid]<x) l=mid+1;
22     }
23     return 0;
24 }
25 
26 int main()
27 {
28     int Case=0;
29     int i,j;
30     while (scanf("%d%d%d",&x,&y,&z)!=EOF)
31     {
32         for(i=0;i<x;i++)
33             scanf("%d",&a[i]);
34         for(i=0;i<y;i++)
35             scanf("%d",&b[i]);
36         for(i=0;i<z;i++)
37             scanf("%d",&c[i]);
38         sort(c,c+z);
39         num=0;
40         for (i=0;i<x;i++)
41         {
42             for (j=0;j<y;j++)
43             {
44                 sum[num++]=a[i]+b[j];
45             }
46         }
47         sort(sum,sum+num);
48         int t,times;
49         scanf("%d",&times);
50         printf("Case %d:
",++Case);
51         while (times--)
52         {
53             scanf("%d",&t);
54             for (i=0;i<z;i++)
55             {
56                 if (find(t-c[i]))
57                 {
58                     printf("YES
");
59                     break;
60                 }
61             }
62             if (i==z)
63                 printf("NO
");
64         }
65     }
66     return 0;
67 }

View Code