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 31 2 31 2 31 2 331410

 

Sample Output

Case 1:NOYESNO

 

Code

1 #include 
          
            2 #include 
           
             3 #define N 500 4 int a[N + 5], b[N + 5], c[N + 5], sumAB[N * N + 5]; 5 int compare(const void *a, const void *b) 6 { 7     return *(int*)a - *(int*)b; 8 } 9 void main()10 {11     int countA, countB, countC, countAB, countX;12     int i, j, x, target;13     int min, max, mid;14     int result, n;15     n = 1;16     while (scanf("%d %d %d", &countA, &countB, &countC) != EOF)17     {18         for (i = 0; i < countA; i++)19             scanf("%d", &a[i]);20         for (i = 0; i < countB; i++)21             scanf("%d", &b[i]);22         for (i = 0; i < countC; i++)23             scanf("%d", &c[i]);24         for (i = 0; i < countA; i++)25             for (j = 0; j < countB; j++)26                 sumAB[i * countB + j] = a[i] + b[j];27         countAB = countA * countB;28         qsort(sumAB, countAB, sizeof(int), compare);29         scanf("%d", &countX);30         for (i = 0; i < countX; i++)31         {32             scanf("%d", &x);33             for (j = 0; j < countC; j++)34             {35                 target = x - c[j];36                 result = 0;37                 min = 0;38                 max = countAB - 1;39                 while (min <= max)40                 {41                     mid = (min + max) / 2;42                     if (sumAB[mid] == target)43                     {44                         result = 1;45                         break;46                     }47                     else if (sumAB[mid] > target)48                         max = mid - 1;49                     else50                         min = mid + 1;51                 }52                 if (result == 1)53                     break;54             }55             if (i == 0)56                 printf("Case %d:\n", n++);57             if (result)58                 printf("YES\n");59             else60                 printf("NO\n");61         }62     }63 }
           
          

 

 

Key Points

Firstly of all, I should be careful. I take a whole afternoon to find the fault which is missing the ":".

Secondly, I should proficient in the binsearch algorithm, whose range is [], and the condition is ≥, and u must add -1 or +1.

Thirdly,  in C, u can only use qsort. and if u want use the function, u must add the head file "#include <stdlib.h>", and the "compare" function.

Fourthly, if u want use function, such strcpy, u should add "#include <string.h>", which is belong to C. And if u want use the type of "string", u should add "#include <string> using namespace std;". Those head files are really different.

Last but not the least, if u want debug, u can remember those short key, likes  Ctrl+F10, which means u can run until the cursor, Shift+F5, which means stop.

 

Recommend

威士忌