Saturday, 27 February 2016

Uva - 10487 - Closest Sums Problem Solution.

Solution: 


#include<bits/stdc++.h>
using namespace std;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
int main(){

    int n,ar[1005],query[30],cas = 0,m;
    vector<int>res;
    while(cin >> n && n != 0){
        cas++;
        for(int i = 0; i < n; i++)cin >> ar[i];
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                res.push_back(ar[i]+ar[j]);
            }
        }
        sort(res.begin(),res.end());
        cin >> m;
        for(int i = 0; i < m; i++)cin >> query[i];
        cout << "Case " << cas << ":" << endl;
        for(int i = 0; i < m; i++){
            for(int j = 1; j < res.size(); j++){
                if(res[j] >= query[i]){
                    if(abs(res[j-1] - query[i]) >= abs(res[j] - query[i]))
                      cout << "Closest sum to " << query[i] << " is " << res[j] << "." << endl;
                    else 
                      cout << "Closest sum to " << query[i] << " is " << res[j-1] << "." << endl;
                    break;
                }
                else if (query[i] >= res[res.size()-1]){
                    cout << "Closest sum to " << query[i] << " is " << res[res.size()-1] << "." << endl;
                    break;
                }
            }
        }
        res.clear();
    }
    return 0;
}

No comments:

Post a Comment