|
По каналу связи передаётся последовательность натуральных чисел –
показания прибора. В течение
N
мин. (
N
– натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической сети и передаёт его на сервер.
Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло
не менее
K
мин.,
а произведение этих трёх чисел было максимально возможным. Запишите в ответе найденное произведение.
Входные данные
Даны два входных файла (файл
A
и файл
B
), каждый из которых
в первой строке содержит натуральное число
K
–
минимальное
количество минут, которое должно пройти между моментами передачи показаний, а во второй – количество переданных показаний
N
(1 ≤
N
≤ 10 000 000,
N
>
K
).
В каждой из следующих
N
строк находится одно натуральное число, не превышающее
10 000 000, которое обозначает значение напряжения в соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла
А
, затем – для файла
B
.
Типовой пример организации данных во входном файле
2
6
5
7
3
1
3
9
При таких исходных данных искомая величина равна 135 – это произведение значений, зафиксированных на первой, третьей
и шестой минутах измерений.
Типовой пример имеет иллюстративный характер.
Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение:
для обработки файла
B
не следует
использовать переборный алгоритм, вычисляющий произведение для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
|