UVa - 10487 - Closest Sums

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم  #####*******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define S 10003
9. using namespace std;
10. typedef long long LL;
11.  
12. vector <int> Number, srt;
13.  
14. int BS(int low, int high, int desiredN){
15.     int mn = INT_MAX, numB, dis;
16.     while(low <= high){
17.         int mid = (low+high)/2;
18.         dis = abs(desiredN-srt[mid]);
19.         if(mn > dis)mn = dis, numB = srt[mid];
20.         if(srt[mid] == desiredN)return desiredN;
21.         if(srt[mid] > desiredN)high = mid-1;
22.         else low = mid+1;
23.     }
24.     return numB;
25. }
26.  
27. void Do(){
28.     int n, N, cs = 0;
29.     while(sc(n) == 1){
30.         if(!n)break;
31.         for(int i = 0; i < n; i++)sc(N), Number.push_back(N);
32.         for(int i = 0; i < n; i++){
33.             for(int j = i+1; j < n; j++){
34.                 srt.push_back(Number[i]+Number[j]);
35.             }
36.         }
37.         sort(srt.begin(), srt.end());
38.         int q, DN;
39.         sc(q);
40.         printf("Case %d:\n", ++cs);
41.         for(int i = 0; i < q; i++){
42.             sc(DN);
43.             int ans = BS(0, srt.size()-1, DN);
44.             printf("Closest sum to %d is %d.\n", DN, ans);
45.         }
46.         Number.clear(), srt.clear();
47.     }
48. }
49.  
50. int main(){
51.     ios_base::sync_with_stdio(0); cin.tie(0);
52.     #ifndef ONLINE_JUDGE
53.     ///freopen("inp","r",stdout);
54.     ///freopen("contest.txt","w",stdout);
55.     #endif
56.     Do();
57.     return 0;
58. }