Feb 27

Раз обещал - выкладываю. Вот они (формат - doc).

PS. Результатов еще нет, но как оказалось, даже первую задачу я решил не полностью.:(

PPS. Результатов до сих пор нет, хотя обещали, что утром они уже будут…

written by fxposter


10 Responses to “Задачи с олимпиады”

  1. 1. djsv Says:

    Мда, первая задачка простенькая, но с подвохом. Кажется, что нужно просто найти три максимальных числа. Но надо не забыть вариант про два минимальных отрицательных и одно максимальное положительное.

  2. 2. FX Poster Says:

    Не только. :) Подумай еще на досуге.
    Hint: если у тебя самое большое из трех максимальных отрицательное?

  3. 3. Андрей Says:

    Тупой, но простой в реализации алгоритм:
    отсортировать массив, а затем перебрать все комбинации из первых трех элементов и трех последних.

  4. 4. FX Poster Says:

    Способ действительно тупой – не наберешь ни одного балла, т.к. программа не пройдет по времени.
    Сортировкой можно получить время O(n log n), а если “простой алгоритм” – то и все O(n * n). А задача вполне решается за O(n).
    PS. Минимальных элементов достаточно двух.

  5. 5. FX Poster Says:

    Набросал тут по быстрому мое “видение решения”.

    
    #include <fstream>
    
    int main()
    {
        unsigned int n;
        int max1 = -1000000001, max2 = -1000000001, max3 = -1000000001;
    	int min1 = 1000000001, min2 = 1000000001;
        int tmp;
        std::fstream file("maxprod.in", std::ios::in);
        file >> n;
        for(unsigned int i = 0; i < n; ++i)
        {
            file >> tmp;
            if(tmp > max1) {
                max3 = max2;
                max2 = max1;
                max1 = tmp;
            } else if(tmp > max2) {
                max3 = max2;
                max2 = tmp;
            } else if(tmp > max3) {
                max3 = tmp;
            }
            if(tmp < min1) {
                min2 = min1;
                min1 = tmp;
            } else if(tmp < min2) {
                min2 = tmp;
            }
        }
        file.close();
        file.open("maxprod.out", std::ios::out);
        if((max2 * max3) > (min1 * min2))
        {
            if(max1 > 0) {
                file << max2 << ' ' << max3 << ' ';
            } else {
                file << min1 << ' ' << min2 << ' ';
            }
        } else {
            if(max1 > 0) {
                file << min1 << ' ' << min2 << ' ';
            } else {
                file << max2 << ' ' << max3 << ' ';
            }
        }
        file << max1;
        file.close();
        return 0;
    }
    
  6. 6. JackYF Says:

    Способ действительно тупой – не наберешь ни одного балла, т.к. программа не пройдет по времени.

    Что я могу сказать – STL рулит.
    Ибо я делал сортировку :) В две строчки. heap_sort :)

    Я, правда, в конце учел не все варианты, да.
    Но 7 баллов из 10 я набрал :).

  7. 7. JackYF Says:

    Это раз. :)

    Два. Твое решение неверно (не по тестам, наверное, но из принципа).
    Дело в том, что произведение двух int’овых чисел в int может запросто не влезть :). И тогда результат сравнения двух произведений не определен.

  8. 8. FX Poster Says:

    Мдя… Забыл, что оно не приводит к максимально возможному типу. :(
    Можно написать так: static_cast<long long>(max2) * max3 и так же с min’ами. Так точно влезет.

  9. 9. Андрей Says:

    >FX Poster
    Вариант действительно тупой, но в условиях не было ограничение на время. Так зачем заморачиваться?

    Кстати в твоем варианте на расмотрен случай когда все числа отрицательные.
    И если попадаются два или более одинаковых числа, то они не учитываются.

    То есть умным способом задача не решена.

  10. 10. FX Poster Says:

    Вариант действительно тупой, но в условиях не было ограничение на время. Так зачем заморачиваться?
    Извиняюсь, что не указал, думал т.к. это олимпиада – будет и так понятно: есть ограничения по времени и размеру занимаемой памяти.

    Далее. Все отрицательные – ну и что? Этот вариант выдаст “max2 max3 max1”, что и будет правильным ответом.

Leave a Reply