Как найти наибольшее произведение трех чисел

Последние несколько задач показывали, что Python удобнее С++, но в этой задаче всё наоборот. Давайте посмотрим.

Если никакие мысли по поводу решения задачи не приходят в голову, то всегда можно написать самое простое решение и позапускать его на разных входных данных. Часто после такого можно найти закономерности или способы сокращения времени работы. В этой задаче можно было бы написать три вложенных цикла и находить максимум.

Можно пойти другим путём. Что было бы, если бы все числа были натуральными? Разумно предположить, что тогда максимальное произведение дали бы три самых больших числа. Супер! Мы уже близки к решению задачи.

Что же меняется, когда появляются отрицательные числа? Лишь то, что произведение двух отрицательных чисел даёт положительное число. То есть, если взять два самых маленьких числа, то произведение может получиться больше, чем у двух самых больших. И всё? Да. А если все числа будут отрицательными? Тогда произведение трёх чисел в любом случае будет отрицательным, а это значит, что нам надо выбрать минимальное по модулю, это можно получить минимальными по модулю множителями (то есть самыми большими из имеющихся чисел).

А в чём же тогда сложность задачи? В размере входных данных. Нам даётся до миллиона чисел. То есть входной файл может быть до 8Мб (7 цифр в числе, знак минус и пробел). И это создаёт две проблемы: объём используемой памяти и время считывания такого количества данных.

Если на Python’е использовать простой список или кортеж, и даже если посылать решение на PyPy, то пройти ограничение по памяти очень сложно. На странице лучших попыток видно, что только 4 человек смогли это сделать. В то время как на С++ можно либо использовать scanf, либо известную каждому олимпиадному программисту на С++ “магическую строку”:

После такого можно вообще не заботиться о скорости в этой задаче, и даже не обращать внимание на асимптотику решения и использовать сортировку:

Главное не забывайте про переполнение типов. Здесь у нас сами числа до 30000, но их произведение уже не помещается в тип int, поэтому в произведении добавлен множитель 1LL (единица типа long long), и тогда компилятор всё произведение считает в типе данных long long.

Конечно же, использование сортировки для поиска трёх максимальных чисел – это излишество, и правильнее находить их за один проход по массиву. Хммм… один проход, а это значит, что нам не надо хранить все данные в оперативной памяти.

Заведём переменные для всех необходимых нам значений:

И будем считывать и сразу обрабатывать входные данные:

Как же найти три максимальных числа? Элементарно. Мы поддерживанием ТОП-3. Если встретили число, которое больше текущего максимума, то тогда обновится весь топ. Но нельзя забывать, что число может быть меньше максимального, но превышать второй (или третий) максимум, тогда обновится соответствующая часть топа.

Аналогично поступаем с поиском двух минимальных чисел:

Ну, а вычисление итогового ответа остаётся почти без изменений:

Если отправить оба решения, то мы увидим сильное уменьшение использованной памяти, и это понятно, потому что теперь мы не храним все числа одновременно. Но вот время работы уменьшилось не очень сильно, потому что при таком размере входных данных основные его расходы именно на считывании:

Сила С++ в его скорости. А если вам удалось сдать задачу на Python, то поделитесь секретом в комментариях, всем будет интересно.

Предыдущий выпуск: Задача 131. Перепись

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