Задание № 7193
Каждую секунду датчик передаёт по каналу связи неотрицательное вещественное число — результат некоторых измерений. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии показаний датчика максимальную сумму двух показаний, между моментами передачи которых прошло не менее 10 секунд. Значение каждого показания датчика не превышает 1000. Общее количество показаний датчика не превышает 10 000.
Напишите на любом языке программирования программу для решения поставленной задачи. Ваша оценка будет зависеть не только от правильности программы, но и от того, насколько она эффективна.
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайт. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Максимальная оценка за правильную программу, неэффективную ни по времени, ни по памяти, — 2 балла. Перед программой укажите версию языка и кратко опишите использованный алгоритм. В первой строке задаётся число N — общее количество показаний прибора. Гарантируется, что N > 10. В каждой из следующих N строк задаётся одно неотрицательное вещественное число — очередное показание датчика.
Пример входных данных:
11
12
45
5
4
25
23
21
20
10
12
26
Программа должна вывести одно число — описанное в условии произведение.
Пример выходных данных для приведённого выше примера входных данных: 38
Содержание верного ответа
Для построения программы, эффективной по времени, можно определить для каждого элемента входных данных максимальное значение от начала данных до этого элемента включительно. Затем нужно складывать каждый элемент, начиная с 11-го, со значением этого максимума, взятого на 10 элементов раньше, и выбрать наибольшую из этих сумм. Чтобы построить программу, эффективную и по времени, по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используется максимум, найденный на 10 элементов раньше, достаточно хранить только 10 последних максимумов. Ниже приводится пример программы, реализующей эту идею
program task32;
const s = 10; {требуемое расстояние между показаниями}
var
N: integer;
a: array[0..s - 1] of real; {хранение показаний прибора}
{k-e введенное число записываем в ячейку a[k mod 3]}
а_: real; {ввод очередного показания}
mx: real; {максимальное введённое число}
{не считая 10 последних}
m: real; {максимальное значение суммы}
i: integer;
begin
readln(N);
{Ввод первых 10 чисел}
for i := 1 to s do
begin
readln(a_);
a[i mod s] := a_
end;
{Ввод остальных значений, поиск максимальной суммы }
mх := -1; т := -1;
for i := s + 1 to N do
begin
readln(a_);
if a[i mod s] > mx then mx := a[i mod s];
if a_ + mx > m then m := a_ + mx;
a[i mod s] : = a_
end;
writeln(m)
end.Нашли ошибку в задании? Выделите фрагмент и нажмите Ctrl + Enter.