Программное решение задач ЕГЭ по информатике

Задача 6798. Источник: Поляков. Задание КИМ 27

Страница задачи 6798

(ЕГЭ-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

Отправить замечание по решению

Код по которому имеется замечание:

Ваш вариант кода:

Комментарий: