Задача 6797. Источник: Поляков. Задание КИМ 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
При таких исходных искомая величина равна 3000 – это произведение значений, зафиксированных на первой, третьей и шестой минутах измерений. Ответ: 3000.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Организуем цикл с минимальной позиции третьего элемента. На каждом шаге будем находить минимальное значение на дистанции 2 * k, минимальное произведение двух значений на дистанции k и минимальное произведение трех значений.
Python
f = open("27-167b.txt")
n, k = map(int, f.readline().split())
a = [int(x) for x in f]
one = 9 * 10 ** 18
two = 9 * 10 ** 18
three = 9 * 10 ** 18
for i in range(2 * k, n):
one = min(one, a[i - 2 * k])
two = min(two, one * a[i - k])
three = min(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-167b.txt');
Reset(f);
Readln(f, n, k);
for i := 1 to n do
Readln(f, a[i]);
one := 9000000000000000000;
two := 9000000000000000000;
three := 9000000000000000000;
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-167b.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 = 9000000000000000000, two = 9000000000000000000, three = 9000000000000000000;
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;
}
Ответ
387672 591081