ЕГЭ−2020, информатика: задания, ответы, решения. Обучающая система Дмитрия Гущина.

Каталог заданий.
Пара на расстоянии не меньше заданного

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word

Задание 27 № 7772

Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов. Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе.

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

Обязательно укажите, что программа является решением задания Б.

Максимальная оценка за правильную программу, эффективную по времени и по памяти — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Входные данные представлены следующим образом. В первой строке задаётся число N — общее количество элементов последовательности. Гарантируется, что N > 8. В каждой из следующих N строк задаётся одно неотрицательное целое число – очередной элемент последовательности.

Пример входных данных:

100

245

Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 2600.

Решение.

Задание Б (решение для задания А приведено ниже, см. программу 3). Для каждого элемента с номером k (нумерацию начинаем с 1), начиная с k = 9, рассмотрим все допустимые по условиям задачи пары, в которых данный элемент является вторым.

Максимальное произведение из всех этих пар будет получено, если первым в паре будет взят максимальный элемент среди всех, от первого и до элемента с номером k-8. Для получения эффективного по времени решения нужно по мере ввода данных помнить максимальное текущее значение, каждое вновь введенное значение умножать на максимум, имевшийся на 8 элементов ранее, и выбрать максимальное из всех таких произведений. Поскольку каждое текущее максимальное значение используется после ввода ещё 8 элементов и после этого становится ненужным, достаточно хранить только 8 последних максимумов. Для этого можно использовать буферный массив из 8 элементов и циклически заполнять его по мере ввода данных.

Размер этого массива не зависит от общего количества введенных элементов, поэтому такое решение будет эффективным не только по времени, но и по памяти. Ниже приводится пример такой программы

Программа 1. Пример правильной и эффективной программы на языке Паскаль:

program N_27;

const d = 8;

var

N: integer;

a: array[0..d-1] of integer; {буфер}

{k-е введенное число записываем в ячейку a[k mod d]}

x: integer;

mx: integer; {максимальное введенное число}

{(не считая 8 последних)}

m: longint; { максимальное значение произведения}

i: integer;

begin

readln(N);

{Ввод первых d чисел}

for i:=1 to d do

begin

readln(x);

a[i mod d] := x

end;

{ Ввод остальных элементов, поиск максимального

произведения}

mx := 0; m := 0;

for i := d + 1 to N do

begin

readln(x);

if a[i mod d] > mx then mx := a[i mod d];

if x * mx > m then m := x * mx;

a[i mod d] := x

end;

writeln(m)

end.

Работа с буферным массивом может быть организована и без использования операции mod, например, циклическим перезаписыванием элементов со сдвигом. Этот способ также является эффективным. Если вместо небольшого массива фиксированного размера (циклического или со сдвигами) хранятся все исходные данные (или все текущие максимумы), программа сохраняет эффективность по времени, но становится неэффективной по памяти, так как требуемая память растёт пропорционально N. Ниже приводится пример такой программы на языке Паскаль. Подобная (и аналогичные по сути) программы оцениваются не выше 3 баллов.

Программа 2. Пример правильной программы на языке Паскаль, эффективной по времени, но неэффективной по памяти:

const d = 8;

var

N: integer;

a: array[1..10000] of integer; {хранение всех

элементов последовательности}

mn:integer; {максимальное введенное число}

{не считая d последних}

m:longint; {максимальное значение произведения}

i: integer;

begin

readln(N);{Ввод всех элементов последовательности}

for i:=1 to N do readln(a[i]);

mn := 0;

m := 0;

for i := d + 1 to N do

begin

if a[i-d] > mn then mn := a[i-d];

if a[i] * mn > m then m := a[i] * mn

end;

writeln(m)

end.

Возможно также переборное решение, в котором находятся произведения всех допустимых пар и из них выбирается максимальное. Ниже приведён пример подобного решения. Это (и аналогичные ему) решение не эффективно ни по времени, ни по памяти. Оно является решением задачи А, но не является решением задания Б. Оценка за такое решение – 2 балла. Программа 3. Пример правильной программы на языке Паскаль, не эффективной ни по времени, ни по памяти:

Const d = 8;

var

N: integer;

a: array[1..10000] of integer;

{хранение всех элементов}

m: longint; {максимальное значение произведения}

i, j: integer;

begin

readln(N);

{Ввод значений элементов}

for i:=1 to N do readln(a[i]);

m := 0;

for i := 1 to N-d do begin

for j := i+d to N do begin

if a[i] * a[j] > m then m := a[i] * a[j];

end;

writeln(m)

end.

Приводим эффективное решение Николая Артюхина на C++.

#include <iostream>

using namespace std;

int main()

{

int n, x, mp=0, ia=0, s=8, a[8], mx=0;

cin >> n;

for(int i=0;i<s;i++){

cin >> a[i];

}

for(int i=s;i<n;i++){

cin >> x;

if(a[ia]>mx) mx = a[ia];

if(x*mx>mp) mp=x*mx;

a[ia]=x;

ia=(ia+1)%s;

}

if(mp!=1000001) cout << mp;

else cout <<"-1";

return 0;

}

Решение · · Видеокурс ·

Сообщить об ошибке · Помощь

Задание 27 № 7799

Для заданной последовательности неотрицательных целых чисел необходимо найти минимальную сумму двух её элементов, номера которых различаются не менее чем на 4. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла. Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Входные данные представлены следующим образом. В первой строке задаётся число N — общее количество элементов последовательности. Гарантируется, что N > 4. В каждой из следующих N строк задаётся одно неотрицательное целое число — очередной элемент последовательности.

Пример входных данных:

245

Программа должна вывести одно число — описанную в условии сумму.

Пример выходных данных для приведённого выше примера входных данных: 20

Решение.

Задание Б (решение для задания А приведено ниже, см. программу 3). Для каждого элемента с номером k (нумерацию начинаем с 1), начиная с k = 5, рассмотрим все допустимые по условиям задачи пары, в которых данный элемент является вторым. Минимальная сумма из всех этих пар будет получена, если первым в паре будет взят минимальный элемент среди всех, от первого и до элемента с номером k-4. Для получения эффективного по времени решения нужно по мере ввода данных помнить минимальное текущее значение, каждое вновь введенное значение складывать с минимумом, имевшимся на 4 элемента ранее, и выбрать минимальную из всех таких сумм.

Поскольку каждое текущее минимальное значение используется после ввода еще 4 элементов и после этого становится ненужным, достаточно хранить только 4 последних минимума. Для этого можно использовать буферный массив из 4 элементов и циклически заполнять его по мере ввода данных.

Программа 1. Пример правильной и эффективной программы на языке Паскаль:

program N_27;

const d = 4;

var

N: integer;

a: array[0..d-1] of integer; {буфер}

{k-е введенное число записываем в ячейку a[k mod d]}

x: integer;

mx: integer; {минимальное введенное число}

{(не считая 4 последних)}

m: integer; { минимальное значение суммы}

i: integer;

begin

readln(N);

{Ввод первых d чисел}

for i:=1 to d do

begin

readln(x);

a[i mod d] := x

end;

{ Ввод остальных элементов, поиск минимальной суммы}

mx := 1001; m := 2001;

for i := d + 1 to N do

begin

readln(x);

if a[i mod d] < mx then mx := a[i mod d];

if x + mx < m then m := x + mx;

a[i mod d] := x

end;

writeln(m)

end.

const d = 4;

var

N: integer;

a: array[1..10000] of integer; {хранение всех

элементов последовательности}

mn:integer; {минимальное введенное число}

{не считая d последних}

m:integer; {минимальное значение суммы}

i: integer;

begin

readln(N);{Ввод всех элементов последовательности}

for i:=1 to N do readln(a[i]);

mn := 1001;

m := 2001;

for i := d + 1 to N do

begin

if a[i-d] < mn then mn := a[i-d];

if a[i] + mn < m then m := a[i] + mn

end;

writeln(m)

end.

Const d = 4;

var

N: integer;

a: array[1..10000] of integer;

{хранение всех элементов}

m: integer; {минимальное значение суммы}

i, j: integer;

begin

readln(N);

{Ввод значений элементов}

for i:=1 to N do readln(a[i]);

m := 2001;

for i := 1 to N-d do begin

for j := i+d to N do begin

if a[i] + a[j] < m then m := a[i] + a[j];

end;

writeln(m)

end.

Приводим эффективное решение Николая Артюхина на C++.

#include <iostream>

using namespace std;

int main()

{

int n, a[4],s=4,mx=1001, ia=0, ms=2001,i, x;

cin >> n;

for(i=0;i<s;i++){

cin >> a[i];

}

for(i=s;i<n;i++){

cin >> x;

if(a[ia]<mx) mx=a[ia]; // if(a[i%s] <mx)

if(x+mx<ms) ms=x+mx;

a[ia]=x; // a[i%s]=x

ia=(ia+1)%s;

}

cout << ms;

return 0;

}

Решение · · Видеокурс ·

Сообщить об ошибке · Помощь

Задание 27 № 8675

Для заданной последовательности целых чисел необходимо найти максимальную сумму квадратов двух её элементов, номера которых различаются не менее чем на 10. Значение каждого элемента последовательности не превышает 100. Количество элементов последовательности не превышает 10000.

Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.

Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.

Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе.

Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А.

Максимальная оценка за выполнение задания А – 2 балла.

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

Обязательно укажите, что программа является решением задания Б.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.

Решение.

Задание Б (решение для задания А приведено ниже, см. программу 3). Для каждого элемента с номером k (нумерацию начинаем с 1), начиная с k = 11, рассмотрим все допустимые по условиям задачи пары, в которых данный элемент является вторым.

Максимальная сумма квадратов элементов этих пар будет получена, если первым в паре будет взят максимальный элемент среди всех, от первого и до элемента с номером k-10. Для получения эффективного по времени решения нужно по мере ввода данных помнить максимальное текущее значение, квадрат каждого вновь введенного значения суммировать с квадратом максимума, найденным на 10 элементов ранее, и выбрать максимальную из всех таких сумм.

Поскольку каждое текущее максимальное значение используется после ввода ещё 10 элементов и после этого становится ненужным, достаточно хранить только 10 последних максимумов. Для этого можно использовать буферный массив из 10 элементов и циклически заполнять его по мере ввода данных.

Размер этого массива не зависит от общего количества введенных элементов, поэтому такое решение будет эффективным не только по времени, но и по памяти.

Ниже приводится пример такой программы

Программа 1. Пример правильной и эффективной программы на языке Паскаль:

pprogram N_27; const d = 10; var N: integer; a: array[0..d-1] of integer; {буфер} {k-е введенное число записываем в ячейку a[k mod d]} x: integer; mx: integer; {максимальное введенное число} {(не считая 10 последних)} m: integer; {максимальное значение суммы квадратов} i: integer; begin readln(N); {Ввод первых d чисел} for i:=0 to d-1 do begin readln(x); a[i mod d] := x end; { Ввод остальных элементов, поиск максимальной суммы квадратов} mx := 0; m := 0; for i := d to N-1 do begin readln(x); if abs(a[i mod d]) > abs(mx) then mx := abs(a[i mod d]); if x*x + mx*mx > m then m := x*x + mx*mx; a[i mod d] := abs(x) end; writeln(m) end.

const d = 10;

var

N: integer;

a: array[1..10000] of integer; {хранение всех

элементов последовательности}

mn:integer; {максимальное введенное число}

{не считая d последних}

m:integer; {максимальное значение суммы квадратов}

i: integer;

begin

readln(N);{Ввод всех элементов последовательности}

for i:=1 to N do readln(a[i]);

mn := 0;

m := 0;

for i := d + 1 to N do

begin

if a[i-d] > mn then mn := a[i-d];

if a[i]*a[i]+mn*mn > m then m := a[i]*a[i]+mn*mn

end;

writeln(m)

end.

Программа 3. Пример правильной программы на языке Паскаль, не эффективной ни по времени, ни по памяти:

Const d = 10;

var

N: integer;

a: array[1..10000] of integer;

{хранение всех элементов}

m: integer; {максимальное значение суммы квадратов}

i, j: integer;

begin

readln(N);

{Ввод значений элементов}

for i:=1 to N do readln(a[i]);

m := 0;

for i := 1 to N-d do begin

for j := i+d to N do begin

if a[i]*a[i]+a[j]*a[j]>m then

m := a[i]*a[i]+a[j]*a[j];

end;

writeln(m)

end.

Решение · · Видеокурс ·

Сообщить об ошибке · Помощь

Задание 27 № 9179

Для заданной последовательности вещественных чисел необходимо найти минимальное среднее арифметическое двух её элементов, номера которых различаются не менее чем на 9. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе.

Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А.

Максимальная оценка за выполнение задания А – 2 балла.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.

Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество элементов последовательности.

Гарантируется, что N > 9. В каждой из следующих N строк задаётся одно неотрицательное целое число – очередной элемент последовательности.

Пример входных данных:

Программа должна вывести одно число – описанное в условии среднее арифметическое.

Пример выходных данных для приведённого выше примера входных данных:

8.5

Решение.

Заметим, что минимальное среднее арифметическое пар элементов равно половине минимальной суммы пар элементов. Поэтому задача сводится к нахождению минимальной суммы элементов на расстоянии, не меньшем 9, которая при печати ответа делится на 2.

Задание Б (решение для задания А приведено ниже, см. программу 3). Для каждого элемента с номером k (нумерацию начинаем с 1), начиная с k = 10, рассмотрим все допустимые по условиям задачи пары, в которых данный элемент является вторым.

Минимальная сумма из всех этих пар будет получена, если первым в паре будет взят минимальный элемент среди всех, от первого и до элемента с номером k-9. Для получения эффективного по времени решения нужно по мере ввода данных помнить минимальное текущее значение, каждое вновь введенное значение складывать с минимумом, найденным на 9 элемента ранее, и выбрать минимальную из всех таких сумм. Поскольку каждое текущее минимальное значение используется после ввода ещё 9 элементов и после этого становится ненужным, достаточно хранить только 9 последних минимумов. Для этого можно использовать буферный массив из 9 элементов и циклически заполнять его по мере ввода данных. Размер этого массива не зависит от общего количества введенных элементов, поэтому такое решение будет эффективным не только по времени, но и по памяти.

Ниже приводится пример такой программы

Программа 1. Пример правильной и эффективной программы на языке Паскаль:

program N_27;const d = 9; var N: integer; a: array[0..d-1] of real; {буфер} {k-е введенное число записываем в ячейку a[k mod d]} x: real; mx: real; {минимальное введенное число} {(не считая 9 последних)} m: real; { минимальное значение суммы} i: integer; begin readln(N); {Ввод первых d чисел} for i:=1 to d do begin readln(x); a[i mod d] := x end; { Ввод остальных элементов, поиск минимальной суммы} mx := 1001.0; m := 2001.0; for i := d + 1 to N do begin readln(x); if a[i mod d] < mx then mx := a[i mod d]; if x + mx < m then m := x + mx; a[i mod d] := x end; writeln(m/2.0) end.

const d = 9;

var

N: integer;

a: array[1..10000] of real; {хранение всех элементов

последовательности}

mn:real; {минимальное введенное число}

{не считая d последних}

m:real; {минимальное значение суммы}

i: integer;

begin

readln(N);{Ввод всех элементов последовательности}

for i:=1 to N do readln(a[i]);

mn := 1001.0;

m := 2001.0;

for i := d + 1 to N do

begin

if a[i-d] < mn then mn := a[i-d];

if a[i] + mn < m then m := a[i] + mn

end;

writeln(m/2.0)

end.

Программа 3. Пример правильной программы на языке Паскаль, не эффективной ни по времени, ни по памяти:

Const d = 9;

var

N: integer;

a: array[1..10000] of real;

{хранение всех элементов}

m: real; {минимальное значение суммы}

i, j: integer;

begin

readln(N);

{Ввод значений элементов}

for i:=1 to N do readln(a[i]);

m := 2001.0;

for i := 1 to N-d do begin

for j := i+d to N do begin

if a[i] + a[j] < m then m := a[i] + a[j];

end;

writeln(m/2.0)

end.

Приводим эффективное решение Игоря Кудашева на Python 3.

n = int(input())

a = []

m = 3000

mx = 3000

for i in range(9):

a.append(int(input()))

for i in range(9, n):

x = int(input())

if a[i % 9] < mx: mx = a[i % 9]

if mx + x < m: m = mx + x

a[i % 9] = x

print(m / 2)

Решение · · Видеокурс ·

Сообщить об ошибке · Помощь

Задание 27 № 9378

В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 10 000. Все числа не превышают 1000. Временем, в течение которого происходит передача, можно пренебречь.

Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным –1.

Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание – 0 баллов. Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.

Обязательноукажите, что программа является решением задания А.

Максимальная оценка за выполнение задания А – 2 балла.

Программа считается эффективной по времени, если время работы

программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.

Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

Обязательно укажите, что программа является решением задания Б.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла. Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.

Пример входных данных:

Программа должна вывести одно число – описанное в условии произведение либо –1, если получить такое произведение не удаётся.

Пример выходных данных для приведённого выше примера входных данных:

Решение.

Задание Б (решение для задания А приведено ниже, см. программу 4). Чтобы произведение было чётным, хотя бы один сомножитель должен быть чётным, поэтому при поиске подходящих произведений чётные показания прибора можно рассматривать в паре с любыми другими, а нечётные – только с чётными.

Для каждого показания с номером k, начиная с k = 7, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k – 6. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное – только чётным.

Для получения эффективного по времени решения нужно по мере ввода данных помнить абсолютное минимальное и минимальное чётное показание на каждый момент времени, каждое вновь полученное показание умножать на соответствующий ему минимум, имевшийся на 6 элементов ранее, и выбрать минимальное из всех таких произведений.

Поскольку каждое текущее минимальное показание используется после ввода ещё 6 элементов и после этого становится ненужным, достаточно хранить только 6 последних минимумов. Для этого можно использовать массив из 6 элементов и циклически заполнять его по мере ввода данных. Размер этого массива не зависит от общего количества введённых показаний, поэтому такое решение будет эффективным не только по времени, но и по памяти. Чтобы хранить абсолютный и чётный минимумы, нужно использовать два таких массива. Ниже приводится пример такой программы, написанной на алгоритмическом языке.

Пример 1. Пример правильной программы на алгоритмическом языке. Программа эффективна и по времени, и по памяти.

алг

нач

цел s = 6 | требуемое расстояние между показаниями

цел amax = 1001 | больше максимально возможного показания

цел N

ввод N

цел a | очередное показание прибора

целтаб мини[0:s-1] | текущие минимумы последних s элементов

целтаб миничет[0:s-1] | чётные минимумы последних s элементов

цел i

| вводим первые s показаний, фиксируем минимумы

цел ма; ма := amax | минимальное показание

цел мчет; мчет := amax | минимальное чётное показание

нц для i от 1 до s

ввод а

ма := imin(ма, a)

если mod(a,2) = 0 то мчет := imin(мчет,a) все

мини[mod(i, s)] := ма

миничет[mod(i, s)] := мчет

кц

цел мп = amax*amax | минимальное значение произведения

цел п

нц для i от s+1 до N

ввод а

если mod(a,2)=0

то п := a * мини[mod(i, s)]

иначе если мчет < amax

то п := a * миничет[mod(i, s)]

иначе п := amax*amax;

все

мп := imin(мп, п)

ма := imin(ма, a)

если mod(a,2) = 0 то мчет := imin(мчет,a) все

мини[mod(i, s)] := ма

миничет[mod(i, s)] := мчет

кц

если мп = amax*amax то мп:=-1 все

вывод мп

кон

Возможны и другие реализации. Например, вместо циклического заполнения массива можно каждый раз сдвигать его элементы. В приведённом ниже примере хранятся и сдвигаются не минимумы, а исходные значения. Это требует чуть меньше памяти (достаточно одного массива вместо двух), но по времени решение со сдвигами менее эффективно, чем с циклическим заполнением. Однако время работы остаётся пропорциональным N, поэтому максимальная оценка за такое решение тоже составляет 4 балла.

Программа 2. Пример правильной программы на языке Паскаль.

Программа использует сдвиги, но эффективна по времени и по памяти

const s = 6; {требуемое расстояние между показаниями}

amax = 1001; {больше максимально возможного показания}

var

N: integer;

a: array[1..s] of integer; {хранение s показаний прибора}

a_: integer; {ввод очередного показания}

ma: integer; {минимальное число без s последних}

me: integer; {минимальное чётное число без s последних}

mp: integer; {минимальное значение произведения}

p: longint;

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.

Если вместо небольшого массива фиксированного размера (циклического или со сдвигами) хранятся все исходные данные (или все текущие минимумы), программа сохраняет эффективность по времени, но становится неэффективной по памяти, так как требуемая память растёт пропорционально N. Ниже приводится пример такой программы на языке Паскаль. Подобные (и аналогичные по сути) программы оцениваются не выше 3 баллов.

Программа 3. Пример правильной программы на языке Паскаль. Программа эффективна по времени, но неэффективна по памяти

const s = 6; {требуемое расстояние между показаниями}

amax = 1001; {больше максимально возможного показания}

var

N, p, i: integer;

a: array[1..10000] of integer; {все показания прибора}

ma: integer; {минимальное число без s последних}

me: integer; {минимальное чётное число без s последних}

mp: integer; {минимальное значение произведения}

begin

readln(N);

{Ввод всех показаний прибора}

for i:=1 to N do readln(a[i]);

ma := amax;

me := amax;

mp := amax*amax;

for i := s + 1 to N do

begin

if a[i-s] < ma then ma := a[i-s];

if (a[i-s] mod 2 = 0) and (a[i-s] < me) then

me := a[i-s];

if a[i] mod 2 = 0 then p := a[i] * ma

else if me < amax then p := a[i] * me

else p := amax * amax;

if (p < mp) then mp := p

end;

if mp = amax*amax then mp := -1;

writeln(mp)

end.

Возможно также переборное решение, в котором находятся произведения всех возможных пар и из них выбирается минимальное. Ниже (см. программу 4) приведён пример подобного решения. Это (и аналогичные ему) решение неэффективно ни по времени, ни по памяти. Оно является решением задания А, но не является решением задания Б. Оценка за такое решение – 2 балла.

Программа 4. Пример правильной программы на языке Паскаль. Программа неэффективна ни по времени, ни по памяти

const s = 6; {требуемое расстояние между показаниями}

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;

if mp = 1000 * 1000 + 1 then mp := -1;

writeln(mp)

end.

Приводим эффективное решение Николая Артюхина на C++.

#include <iostream>

using namespace std;

int main()

{

int n, x, mp=1000001, ia=0, s=6, a[6], mn=1001, mch=1001;

cin >> n;

for(int i=0;i<s;i++){

cin >> a[i];

}

for(int i=s;i<n;i++){

cin >> x;

if((a[ia]%2==0)&&(a[ia]<mch)) mch = a[ia];

else if ((a[ia]%2!=0)&&(a[ia]<mn)) mn = a[ia];

if(x%2==0){

if((x*mn<x*mch)&&(x*mn<mp)) mp = x*mn;

else if ((x*mch<x*mn)&&(x*mch<mp)) mp=x*mch;

}

else if ((x%2!=0)&&(x*mch<mp)) mp=x*mch;

a[ia]=x;

ia=(ia+1)%s;

}

if(mp!=1000001) cout << mp;

else cout <<"-1";

return 0;

}

Приводим эффективное решение Александра Цыганкова на Python.

a = []

n = int(input())

m = 10 ** 7

mx = 10 ** 7

mx1 = 10 ** 7

for i in range(6):

a.append(int(input()))

for i in range(6, n):

x = int(input())

if a[i % 6] % 2 == 0 and a[i % 6] < mx:

mx = a[i % 6]

elif a[i % 6] % 2 != 0 and a[i % 6] < mx1:

mx1 = a[i % 6]

if x % 2 == 0 and min(mx, mx1) * x < m:

m = min(mx, mx1) * x

elif x % 2 != 0 and mx * x < m:

m = mx * x

a[i % 6] = x

if m == 10 ** 7:

print(-1)

else:

print(m)

Аналоги к заданию № 9378: 12443 Все

Источник: Демонстрационная версия ЕГЭ—2016 по информатике.

Решение · · Видеокурс ·

Сообщить об ошибке · Помощь

Пройти тестирование по этим заданиям