UVa 10487 - Closest Sums

 10487 - Closest Sums

#include<bits/stdc++.h>

using namespace std;

long long arr[1010];

long long sum[1000009];

long long closestSum1(long long q, long long c)

{

long long l=-1,r=c,m;

while(r>l+1)

{

m=(l+r)/2;

if(sum[m]<=q) l=m;

else r=m;

}

return l;

}

int main()

{

long long n,i,k,l,m,z=1,query,j,q;

while(scanf("%lld",&n)&&n)

{

for(i=0;i<n;i++)

{

scanf("%lld",&arr[i]);

}

long long c=0;

for(i=0;i<n-1;i++)

{

for(j=i+1;j<n;j++)

{

sum[c]=arr[i]+arr[j];

c++;

}

}

sort(sum,sum+c);

scanf("%lld",&query);

printf("Case %lld:\n",z);

for(j=1;j<=query;j++)

{

scanf("%lld",&q);

if(q<=sum[0]) printf("Closest sum to %lld is %lld.\n",q,sum[0]);

else if(q>=sum[c-1]) printf("Closest sum to %lld is %lld.\n",q,sum[c-1]);

else

{

long long x=closestSum1(q,c);

if(abs(q-sum[x])<abs(sum[x+1]-q)) printf("Closest sum to %lld is %lld.\n",q,sum[x]);

else printf("Closest sum to %lld is %lld.\n",q,sum[x+1]);

}

}

z++;

}

return 0;

}