UVa 10487 - Closest Sums

// UVa 10487 - Closest Sums

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <math.h>
using namespace std;

#define integer signed long long

vector<integer> v;

int bsearch(int ini, int fin, integer q) {
	if (ini == fin)
		return ini;
	int mid = (ini + fin) >> 1;
	if (v[mid] < q)
		return bsearch(mid + 1, fin, q);
	else
		return bsearch(ini, mid, q);
}

int main() {
	int t = 0, n;
	while ((cin >> n) && n) {
		t++;
		integer a[1000];
		v.clear();
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			for (int j = 0; j < i; j++)
				if (a[i] != a[j])
					v.push_back(a[i] + a[j]);
		}
		sort(v.begin(), v.end());
		int m;
		printf("Case %d:\n", t);
		for (cin >> m; m; m--) {
			integer q;
			cin >> q;
			int p = bsearch(0, v.size() - 1, q);
			int c = p;
			while (c > 0 && v[c] == v[p])
				c--;
			int d = p;
			while (d < v.size() - 1 && v[d] == v[p])
				d++;
			integer cc = abs(v[c] - q);
			integer cd = abs(v[d] - q);
			integer cp = abs(v[p] - q);
			int sol;
			if (cc < cd && cc < cp)
				sol = c;
			else if (cd < cp)
				sol = d;
			else
				sol = p;
			printf("Closest sum to %lld is %lld.\n", q, v[sol]);
		}
	}
	return 0;
}