Задание № 7205
Датчик передаёт каждую секунду по каналу связи неотрицательное целое число, не превосходящее 1000 — текущий результат измерений. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо найти в заданной серии показаний датчика минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 15 секунд. Если получить такое произведение не удаётся, ответ считается равным — 1. Общее количество показаний датчика в серии не превышает 10 000.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А — 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа А и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Входные данные представлены следующим образом. В первой строке задаётся число N — общее количество показаний датчика. Гарантируется, что N > 15. В каждой из следующих N строк задаётся одно неотрицательное целое число — очередное показание прибора.
Пример входных данных
<p>17</p><p>5</p><p>4</p><p>3</p><p>2</p><p>1</p><p>6</p><p>7</p><p>8</p><p>9</p><p>10</p><p>110</p><p>120</p><p>130</p><p>140</p><p>150</p><p>160</p><p>50</p>Программа должна вывести одно число — описанное в условии произведение, либо -1, если получить такое произведение не удаётся.
Пример выходных данных для приведённого выше примера входных данных: 200
Содержание верного ответа
Задание А
Ниже приводится пример переборного решения на Паскале, не эффективного ни по памяти, ни по времени, но являющимся правильным ответом на задание А.
Программа 1.
const s = 15; {требуемое расстояние между показаниями} var N: integer; a: array[1..10000] of integer; {все показания датчика} mp: integer; {минимальное значение произведения} i, j: integer; begin readln(N); {Ввод значений датчика} for i := 1 to N do readln(a [i]); mp := 1000 * 1000 + 1; for i := 1 to N - s do begin for j := i + s to N do begin if (a[i] * a[j] mod 2 = 0) and (a[i] * a[j] < mp) then mp := a[i] * a[j] end; end; if mp = 1000 * 1000 + 1 then mp := -1; writeln(mp) end.Задание Б
Чтобы произведение было чётным, хотя бы один сомножитель должен быть чётным, поэтому при поиске подходящих произведений чётные показания прибора можно рассматривать в паре с любыми другими, а нечётные — только с чётными.
Для каждого показания с номером k, начиная с k = 16, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k — 15. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное — только чётным.
Для получения эффективного по времени решения нужно по мере ввода данных помнить абсолютное минимальное и минимальное чётное показание на каждый момент времени, каждое вновь полученное показание умножать на соответствующий ему минимум, имевшийся на 15 элементов ранее, и выбрать минимальное из всех таких произведений. Ниже приводится пример такой программы на Паскале, эффективной по памяти и по времени.
Программа 2.
const s = 15; {требуемое расстояние между показаниями} аmах = 1001;{больше максимально возможного показания}var. N: integer; a: array[l..s] of integer; {хранение s показаний датчика} а_: integer; {ввод очередного показания} mа: integer; {минимальное число без s последних} mе: integer; {минимальное чётное число без s последних} mp: integer; {минимальное значение произведения} р: integer; i, j : integer;begin readln(N); {Ввод первых s чисел} for i := 1 to s do readln(a[i]); {Ввод остальных значений, поиск минимального произведения} mа : = аmах; те : = аmах; mр := аmах * аmах; for i := s + 1 to N do begin readln(a ); if a[l] < mа then mа := a[1]; if (a [1] mod 2 = 0) and (a[1] < me) then me := a[1]; if a_ mod 2 = 0 then p := a * mа else if me < amax then p := a_ * me else p := amax * amax; if (p < mp) then mp := p; {сдвигаем элементы вспомогательного массива влево} for j := 1 to s = 1 do a[j] := a[j + 1]; a[s] := a_ end; if mp = amax * amax then mp := -1; writeln(mp)end.Нашли ошибку в задании? Выделите фрагмент и нажмите Ctrl + Enter.