Датчик передаёт каждую секунду по каналу связи неотрицательное целое число, не превосходящее 1000 — текущий результат измерений. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо найти в заданной серии показаний датчика минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 15 секунд. Если получить такое произведение не удаётся, ответ считается равным -1. Общее количество показаний датчика в серии не превышает 10 000.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.
Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Входные данные представлены следующим образом. В первой строке задаётся число N — общее количество показаний датчика. Гарантируется, что N > 15. В каждой из следующих N строк задаётся одно неотрицательное целое число — очередное показание прибора.
Пример входных данных:
17
5
4
3
2
1
6
7
8
9
10
110
120
130
140
150
160
50
Программа должна вывести одно число — описанное в условии произведение, либо −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; {требуемое расстояние между показаниями}
amax = 1001; {больше максимально возможного показания}
var
N: integer;
a: array[1..s] of integer; {хранение s показаний датчика}
a_: integer; {ввод очередного показания}
ma: integer; {минимальное число без s последних}
me: integer; {минимальное чётное число без s последних}
mp: integer; {минимальное значение произведения}
p: integer;
i, j: integer;
begin
readln(N);
{Ввод первых s чисел}
for i:=1 to s do readln(a[i]);
{Ввод остальных значений, поиск минимального произведения}
ma := amax; me := amax;
mp :=amax*amax;
for i := s + 1 to N do begin
readln(a_);
if a[1] < ma then ma := a[1];
if (a[1] mod 2 = 0) and (a[1] < me) then me := a[1];
if a_ mod 2 = 0 then p := a_ * ma
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.
Приводим решение Х. Котова на Python 3.
n = int(input())
left = int(input())
answer=100000001
a = [int(input()) for i in range(14)]
for с in range(n - 15):
right = int(input())
if left%2==0 or right%2==0 and left*right < answer:
answer=left*right
if a[0] < left:
left=a[0]
a.pop(0)
a.append(right)
if answer==100000001:
answer=-1
print(answer)
Приводим эффективное решение Даниила Менькина на C++.
#include "pch.h"
#include using namespace std; int main() { int x, i, k, N, minpr = 1000001, nchmin = 1001, chetmin = 1001, absolutmin = 1001; int a[15]; // С помощью этого массива будем соблюдать промежуток в 15 измерений cin >> N; for (i = 0; i < 15; i++) // Вводим первые 15 показаний { cin >> a[i]; } N −= 15; for (i = 0; i < N; i++) // Продолжаем вводить показания { cin >> x; k = i % 15; // k — номер показания в массиве a[15], которое было получено 15 замеров назад if ((a[k] % 2 == 1) && (a[k] < nchmin)) // Ищем нечетный миниум, полученный как миниум 15 замеров назад nchmin = a[k]; else if (a[k] < chetmin) // Теперь четный chetmin = a[k]; a[k] = x; // Заменяем в массиве k показатель на нынешний if (chetmin < nchmin) // Находим абсолютный миниум absolutmin = chetmin; else absolutmin = nchmin; if ((x % 2 == 1) && ((x * chetmin) < minpr)) // Если показание нечетное, то четное произведение получим с помощью четного миниума minpr = x * chetmin; else if ((x % 2 == 0) && ((x * absolutmin) < minpr)) minpr = x * absolutmin; } if (minpr < 1000001) // Было ли получено произведение cout << minpr; else cout << − 1; return 0;
Приводим эффективное решение Николая Артюхина на C++.
#include <iostream>
using namespace std;
int main()
{
int a[15], n, x, i, mp=1000001, mch=1001, mnch=1001, min=1001, s=15,k;
cin >> n;
for(i=0;i<s;i++){
cin >> a[i];
}
for(i=s;i<n;i++){
cin >> x;
k=i%s;
if((a[k]%2==0)&&(a[k]<mch)) mch=a[k];
else if((a[k]%2!=0)&&(a[k]<mnch)) mnch=a[k];
if(mch>mnch) min=mnch;
else min=mch;
if((x%2==0)&&(x*min<mp)) mp=x*min;
else if((x%2!=0)&&(x*mch<mp)) mp=x*mch;
a[k]=x;
}
if(mp!=1000001) cout << mp;
else cout << "-1";
return 0;
}
Предлагаю нормальное (даже изящное) решение на Python 3:
n = int(input())
left = int(input())
answer=100000001
a = [int(input()) for i in range(14)]
for с in range(n - 15):
right = int(input())
if left%2==0 or right%2==0 and left*right<answer:
answer=left*right
if a[0]<left:
left=a[0]
a.pop(0)
a.append(right)
if answer==100000001:
answer=-1
print(answer)