Can you find it?

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

Total Submission(s): 3758    Accepted Submission(s): 935

Problem 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

 

 

这题是题好二分，要把两个数组合拼成一个。一个小地方错（代码里注明），让我找半天都找不到那里错。晕呀。。。现在还要搞清楚while(l < (=)r)的等号有与没的区别还有l = mid + 1和r = mid (- 1)要不要1。

还有如果数组从1...n和0...n-1的区别。要把这个弄清楚。

 

 

1 #include 
        
           2 #include 
         
            3 #define maxn 505  4  5 int a[maxn], b[maxn], c[maxn], ab[maxn*maxn];  6 int l, n, m;  7  8 int Cmp(const void *a, const void *b)  9 {
      10     return *(int *)a - *(int *)b; 11 } 12 13 int F(int n, int k) 14 {
      15     int l, r, mid; 16     l = 0; 17     r = k - 1;//当时就是这里没多加个变量k,而直接l * m，搞得一直WA 18     while (l < r) 19     {
      20         mid = (l + r) / 2; 21         if (ab[mid] == n) 22         {
      23             return 1; 24         } 25         if (ab[mid] > n) 26         {
      27             r = mid; 28         } 29         else 30         {
      31             l = mid + 1; 32         } 33     } 34     return 0; 35 } 36 37 38 int main() 39 {
      40     int   i, j, k, times = 1, flag, s, x; 41     42     while (scanf("%d%d%d", &l, &m, &n) != EOF) 43     {
      44         for (i = 0; i < l;scanf("%d", &a[i++])); 45         for (j = 0; j < m;scanf("%d", &b[j++])); 46         for (k = 0; k < n;scanf("%d", &c[k++])); 47         48         49         k = 0; 50         for (i = 0; i < l; i++) 51         {
      52             for (j = 0; j < m; j++) 53             {
      54                 ab[k++] = a[i] + b[j]; 55             } 56         } 57         qsort(ab, k, sizeof(ab[0]), Cmp); 58 59         printf("Case %d:\n", times++); 60         scanf("%d", &s); 61 62         while (s--) 63         {
      64             scanf("%d", &x); 65             flag = 1; 66             for (i = 0; i < n; i++) 67             {
      68                 if (F(x - c[i], k) == 1) 69                 {
      70                     flag = 0; 71                     break; 72                 } 73             } 74             if (flag == 0) 75             {
      76                 puts("YES"); 77             } 78             else 79             {
      80                 puts("NO"); 81             } 82         } 83     } 84     85     return 0; 86 }