Решение задачи SimpleGuess с TopCoder

Постановка задачи

Задача SimpleGuess
Кратко смысл задачи вот в чем: есть загаданные числа X и Y; также есть массив натуральных чисел, в котором есть элементы со значениями X+Y и X-Y; нужно возвратить максимально возможное X*Y. Причем тот, кто загадывал числа предпочитает, чтобы они были большими.

Анализ

Рассмотрим вектор из примера: 1 4 5 8 (Ответ: 6)
Шесть можно получить как: 2*3 или 3*2
Проверяем 3-2=1 есть в векторе, 3+2=5 есть в векторе

Решение

Рассуждаю так значит чтобы произведение X*Y было максимальным множители (которые пока еще слагаемые) тоже должны быть максимальными. Т.к. X+Y дает самое большое подходящее нам число в массиве то искать надо от него. Примерно так:

for x = max-1 downto 1 do begin
    y = max - x
    // если x и y принадлежат вектору и являются 
    // «большими числами» то это то что на нужно
end

Только возникает вопрос как определить что числа X’ и Y’ больше чем X и Y? Я придумал так
abs(X’ - Y’) < abs(X - Y)
Например 5 и 4 или 10 и 2
|5-4| < |10-2| значит 5 и 4 больше

Программирование

#include <vector>
#include <algorithm>
using namespace std;
class SimpleGuess {
    private:
    bool e(vector <int> hints, int n) {
        for (int i = hints.size()-1; i >= 0; i--)
            if (hints[i] == n)
                return true;
        return false;
    }
    public:
    SimpleGuess(void) {};
    ~SimpleGuess(void) {};
    int getMaximum(vector <int> hints) {
        int x_ = 1, y_ = 1;
        bool first = true;
        sort(hints.begin(), hints.end());
        for (int i = hints.size()-1; i >= 0; i--) {
            for (int x = hints[i]-1; x > 0; x--) {
                int y = hints[i] - x;
                if (e(hints, x+y) && e(hints, x-y)) {
                    if (first) { x_ = x; y_ = y; first = false; }
                    if ( (x*y > x_*y_) 
                        && (abs(x - y) < abs(x_ - y_)) ) {
                    x_ = x; y_ = y;
                    }
                }
            }
        }
        return x_*y_;
    }
};

Выводы

Функцию принадлежности вектора писал самостоятельно. Хотя можно было использовать STL

if (std::find(v.begin(), v.end(),value)!=v.end())

А если учитывать что вектор у меня был отсортирован то можно было еще лучше

if (std::binary_search(v.begin(), v.end(), value)

Окончательный вариант:

#include <vector>
#include <algorithm>
using namespace std;
    class SimpleGuess {
    private:
    public:
    SimpleGuess(void) {};
    ~SimpleGuess(void) {};
    int getMaximum(vector <int> hints) {
        int x_ = 1, y_ = 1;
        bool first = true;
        sort(hints.begin(), hints.end());
        for (int i = hints.size()-1; i >= 0; i--) {
            for (int x = hints[i]-1; x > 0; x--) {
                int y = hints[i] - x;
                if (binary_search(hints.begin(), hints.end(), x+y) 
                    && binary_search(hints.begin(), hints.end(), x-y))
                {
                    if (first) { x_ = x; y_ = y; first = false; }
                    if ( (x*y > x_*y_) 
                        && (abs(x - y) < abs(x_ - y_)) ) { x_ = x; y_ = y; }
                }
            } // x
        } // i
        return x_*y_;
    }
};

Работа над ошибками

Если компилятор на арене выдает такое сообщение, то это значит, что в функции не всегда возвращается значение.

Your code compiled successfully, but generated warnings:

Your class or method was improperly declared: In function 
‘int _wrapper::thunk(std::vector<int, std::allocator<int> >)’:

Your class or method was improperly declared:20034: warning: 
control may reach end of non-void function 
‘int SimpleGuess::getMaximum(std::vector<int, std::allocator<int> >)’ 
being inlined

 
Теги: