Решение: Максимальное произведение показаний
По каналу связи передаётся последовательность натуральных чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение напряжения в электрической сети и передаёт его на сервер. Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее $K$ минут, а произведение этих трёх чисел было максимально возможным. Для выполнения задания используйте данные из прилагаемых файлов A и B.
Решение по шагам
5 шаговПронумеруем показания начиная с нуля. Если последнее выбранное показание имеет индекс $i$, два предыдущих должны находиться среди позиций от $0$ до $i-K$.
Будем поддерживать для разрешённого префикса максимум одного числа $M_1$ и максимум произведения двух чисел $M_2$. При добавлении нового показания $a_i$ сначала добавляем в структуры число $a_{i-K}$ и обновляем $M_1$ и $M_2$.
Для текущего показания возможное произведение трёх чисел равно $M_2 \cdot a_i$. Максимум таких произведений по всем позициям является ответом для файла.
Алгоритм выполняется за $O(N)$ времени и использует $O(1)$ дополнительной памяти, если обрабатывать входной файл последовательно и хранить очередь из последних $K$ показаний.
Числа могут иметь до 21 цифры, поэтому при реализации следует использовать целочисленный тип достаточной разрядности или длинную арифметику.
Численные ответы зависят от данных файлов A и B, которые в условии не представлены.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверять все тройки показаний перебором.
Разрешать выбирать показания на расстоянии менее $K$ минут.
Обновлять максимум пары до добавления показания, которое ещё нельзя использовать.
Использовать 32-битный целочисленный тип для произведения.