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