Задача 6798. Источник: Поляков. Задание КИМ 27
(ЕГЭ-2023) По каналу связи передаётся последовательность целых чисел - показания прибора. В течение N минут (N – натуральное число) прибор ежеминутно регистрирует значение силы тока (в условных единицах) в электрической сети и передаёт его на сервер. Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее К минут, а произведение этих чисел было максимально возможным. Запишите в ответе остаток от деления найденного произведения на 106 + 1.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (1 < N ≤ 10 000 000) – количество переданных показаний, и натуральное число К (K < N) – минимальное количество минут, которое должно пройти между моментами передачами любых двух из трёх показаний. В каждой из следующих N строк находится одно натуральное число, не превышающее 10 000 000, которое обозначает значение силы тока в соответствующую минуту.
Пример входного файла:
6 2
15
14
20
23
21
10
При таких исходных искомая величина равна 6300 – это произведение значений, зафиксированных на первой, третьей и пятой минутах измерений. Ответ: 6300.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Делаем перебор по индексам третьего элемента. На каждом шаге находим максимальный элемент на дистанции 2 * k, максимальное произведение двух элементов на дистанции k и максимальное произведение трех элементов.
Python
f = open("27-168b.txt")
n, k = map(int, f.readline().split())
a = [int(x) for x in f]
one = 0
two = 0
three = 0
for i in range(2 * k, n):
one = max(one, a[i - 2 * k])
two = max(two, one * a[i - k])
three = max(three, two * a[i])
print(three % 1000001)
PascalABC
var
n, k, i: Integer;
one, two, three: Int64;
a: array [1..170656] of Integer;
f: TEXT;
begin
Assign(f, '27-168b.txt');
Reset(f);
Readln(f, n, k);
for i := 1 to n do
Readln(f, a[i]);
one := 0;
two := 0;
three := 0;
for i := 2 * k + 1 to n do
begin
if a[i - 2 * k] > one then
one := a[i - 2 *k];
if one * a[i - k] > two then
two := one * a[i - k];
if two * a[i] > three then
three := two * a[i];
end;
Writeln(three mod 1000001);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-168b.txt");
int n, k;
f >> n >> k;
int* a = new int[n];
for (int i = 0; i < n; i++)
f >> a[i];
long long one = 0, two = 0, three = 0;
for (int i = 2 * k; i < n; i++)
{
if (a[i - 2 * k] > one)
one = a[i - 2 * k];
if (one * a[i - k] > two)
two = one * a[i - k];
if (two * a[i] > three)
three = two * a[i];
}
cout << three % 1000001 << endl;
delete[] a;
}
Ответ
519386 298243