IMPA/p11968/p11968.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include <iomanip>
#include <sstream>
#include <climits>
#include <queue>
#include <list>
#include <cmath>

using namespace std;

typedef long long int nat;

int main()
{
    nat num_tests, num_items, num_cakes, num_drinks;

    cin >> num_tests;

    for(nat test = 0; test < num_tests; ++test)
    {
        cin >> num_items >> num_cakes >> num_drinks;

        nat sum_prices = 0;
        vector<nat> cake_price(num_cakes);
        vector<nat> drink_price(num_drinks);

        for(nat i = 0; i < num_items; ++i)
        {
            nat price;
            cin >> price;
            sum_prices += price;
            if(i < num_cakes)
            {
                cake_price[i] = price;
            }
            else if(i < num_cakes+num_drinks)
            {
                drink_price[i-num_cakes] = price;
            }
        }

//        for(auto i : cake_price)
//        {
//            cout << "Cake price: " << i << endl;
//        }
//
//        for(auto i : drink_price)
//        {
//            cout << "Drink price: " << i << endl;
//        }

        const unsigned int FIXED_PRECISION = 3;
        double avg = (double)sum_prices / num_items;
        long long int avg_fixed_point = round(avg*(1<<FIXED_PRECISION));

//        cout << "Average: " << avg << endl;
//        cout << "Average fixed: " << (avg_fixed_point) << endl;

        pair<nat, nat> cake(0,LLONG_MAX), drink(0,LLONG_MAX);


        for(nat i = 0; i < num_cakes+num_drinks; ++i)
        {
            if(i < num_cakes)
            {
                //cout << abs((cake_price[i]<<FIXED_PRECISION)-avg_fixed_point) << " < " << abs(cake.second-avg_fixed_point) << " && " << (cake_price[i]<<FIXED_PRECISION) << " < " << cake.second << endl;
                if(abs((cake_price[i]<<FIXED_PRECISION)-avg_fixed_point) < abs(cake.second-avg_fixed_point))
                {
                    // Found closer cake!
                    cake.first = i;
                    cake.second = (cake_price[i]<<FIXED_PRECISION);
                }
                else if(abs((cake_price[i]<<FIXED_PRECISION)-avg_fixed_point) == abs(cake.second-avg_fixed_point) && (cake_price[i]<<FIXED_PRECISION) < cake.second)
                {
                    // Found cheaper cake!
                    cake.first = i;
                    cake.second = (cake_price[i]<<FIXED_PRECISION);
                }
            }
            else
            {
                //cout << "i: " << i << endl << abs((drink_price[i-num_cakes]<<FIXED_PRECISION)-avg_fixed_point) << " < " << abs(drink.second-avg_fixed_point) << " && " << (drink_price[i-num_cakes]<<FIXED_PRECISION) << " < " << drink.second << endl;
                if(abs((drink_price[i-num_cakes]<<FIXED_PRECISION)-avg_fixed_point) < abs(drink.second-avg_fixed_point))
                {
                    // Found closer drink!
                    drink.first = i-num_cakes;
                    drink.second = (drink_price[i-num_cakes]<<FIXED_PRECISION);
                }
                else if(abs((drink_price[i-num_cakes]<<FIXED_PRECISION)-avg_fixed_point) == abs(drink.second-avg_fixed_point) && (drink_price[i-num_cakes]<<FIXED_PRECISION) < drink.second)
                {
                    // Found cheaper drink!
                    drink.first = i-num_cakes;
                    drink.second = (drink_price[i-num_cakes]<<FIXED_PRECISION);
                }
            }
        }
        cout << "Case #" << test+1 << ": " << (cake.second>>FIXED_PRECISION) << " " << (drink.second>>FIXED_PRECISION) << endl;

    }

    return 0;
}