Блог FX’а

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

1. 1. djsv Says:
   March 4th, 2007 at 18:22

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

2. 2. FX Poster Says:
   March 4th, 2007 at 18:46

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

3. 3. Андрей Says:
   March 5th, 2007 at 08:34

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

4. 4. FX Poster Says:
   March 6th, 2007 at 00:22

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

5. 5. FX Poster Says:
   March 6th, 2007 at 00:23

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

   
   #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:
   March 6th, 2007 at 02:04

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

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

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

7. 7. JackYF Says:
   March 6th, 2007 at 02:06

   Это раз. :)

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

8. 8. FX Poster Says:
   March 6th, 2007 at 15:38

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

9. 9. Андрей Says:
   March 7th, 2007 at 10:41

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

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

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

10. 10. FX Poster Says:
    March 7th, 2007 at 11:12

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

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

Leave a Reply

Name (required)

Mail (will not be published) (required)

Website

Subscribe to comments