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