ЕГЭ–2026, информатика: задания, ответы, решения

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

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

Тип Д27 C4 № 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;

}

Критерии проверки:

Пояснения для проверяющих.

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

2. Два задания и, соответственно, возможность для экзаменуемого представить две программы дают ученику возможность (при его желании) сначала написать менее сложное и менее эффективное решение (задание А), которое даёт ему право получить два балла, а затем приступить к поиску более эффективного решения.

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

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трех синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано или пропущено зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, недопустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку.	4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Количество синтаксических ошибок (описок) указанных выше видов — не более пяти. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер priority_queue, vector, set или map в С++)). Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы в «экзотических» ситуациях. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок: 1) ошибка при инициализации минимумов; 2) неверно обрабатывается ситуация, когда один или несколько миниимумов не определены; 3) допущен выход за границу массива; 4) используется знак < вместо <=, or вместо and и т. п.	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма есть до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических описок не должно быть более девяти. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве и перебираются все возможные пары элементов последовательности: min := 2001; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i]+a[j]) mod 2 = 1) and (a[i]+a[j] < min) then min := a[i]+a[j]; end end;	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может отсутствовать или быть представленной отдельными фрагментами, без ограничений на количество ошибок.	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4

Решение · Критерии · Помощь

Тип Д27 C4 № 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;

}

Критерии проверки:

Говоря неформально, 4 балла ставится за эффективную и правильно работающую программу, которая, возможно, содержит до трех синтаксических ошибок (описок). 3 балла ставится в случае, когда фактически задача решена, но

количество описок более трех (но не более пяти) и допущено не более одной содержательной ошибки, не позволяющей усомниться в том, что экзаменуемый правильно придумал алгоритм (список допустимых ошибок приведен ниже). 2 балла ставится, если в дополнение к неточностям, которые перечислены выше, программа работает неэффективно по времени и/или допущено до трех упомянутых выше содержательных ошибок. Количество допустимых описок — до семи. 1 балл ставится, если программа написана неверно, но из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи. Далее сказанное уточнено.

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трех синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано или пропущено зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, недопустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку.	4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Количество синтаксических ошибок (описок) указанных выше видов — не более пяти. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер priority_queue, vector, set или map в С++)). Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы в «экзотических» ситуациях. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок: 1) ошибка при инициализации минимумов; 2) неверно обрабатывается ситуация, когда один или несколько миниимумов не определены; 3) допущен выход за границу массива; 4) используется знак < вместо <=, or вместо and и т. п.	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма есть до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических описок не должно быть более девяти. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве и перебираются все возможные пары элементов последовательности: min := 2001; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i]+a[j]) mod 2 = 1) and (a[i]+a[j] < min) then min := a[i]+a[j]; end end;	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может отсутствовать или быть представленной отдельными фрагментами, без ограничений на количество ошибок.	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4

Решение · Критерии · Помощь

Тип Д27 C4 № 8115 Добавить в вариант

На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи неотрицательное целое число  — количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии показаний прибора минимальное

нечётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным −1. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

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

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

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

Перед программой укажите версию языка программирования. ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А  — 2 балла.

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

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

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

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти,  — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти,  — 3 балла.

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

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

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

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

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

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трех синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано или пропущено зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, недопустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку.	4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Количество синтаксических ошибок (описок) указанных выше видов — не более пяти. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных). Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы в «экзотических» ситуациях. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок: 1) ошибка при инициализации максимумов; 2) неверно обрабатывается ситуация, когда один или несколько максимумов не определены (все или все, кроме одного, элементы исходных данных имеют одинаковую чётность); 3) допущен выход за границу массива; 4) используется знак < вместо <=, or вместо and и т. п.	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но в реализации алгоритма есть до трёх содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических «описок» не должно быть более девяти. Программа может быть неэффективна по времени.	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может отсутствовать или быть представленной отдельными фрагментами, без ограничений на количество ошибок.	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4

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

Источник: ЕГЭ 05.05.2015. Досрочная волна

Решение · Критерии · 1 комментарий · Помощь

Тип Д27 C4 № 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.

Критерии проверки:

Пояснения для проверяющих.

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трех синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано или пропущено зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, недопустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку.	4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Количество синтаксических ошибок (описок) указанных выше видов — не более пяти. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер priority_queue, vector, set или map в С++)). Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы в «экзотических» ситуациях. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок: 1) ошибка при инициализации минимумов; 2) неверно обрабатывается ситуация, когда один или несколько миниимумов не определены; 3) допущен выход за границу массива; 4) используется знак < вместо <=, or вместо and и т. п.	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма есть до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических описок не должно быть более девяти. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве и перебираются все возможные пары элементов последовательности: min := 2001; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i]+a[j]) mod 2 = 1) and (a[i]+a[j] < min) then min := a[i]+a[j]; end end;	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может отсутствовать или быть представленной отдельными фрагментами, без ограничений на количество ошибок.	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4

Решение · Критерии · Помощь

Тип Д27 C4 № 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(float(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)

Критерии проверки:

Пояснения для проверяющих.

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трех синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано или пропущено зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, недопустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку.	4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Количество синтаксических ошибок (описок) указанных выше видов — не более пяти. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер priority_queue, vector, set или map в С++)). Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы в «экзотических» ситуациях. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок: 1) ошибка при инициализации минимумов; 2) неверно обрабатывается ситуация, когда один или несколько миниимумов не определены; 3) допущен выход за границу массива; 4) используется знак < вместо <=, or вместо and и т. п.	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма есть до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических описок не должно быть более девяти. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве и перебираются все возможные пары элементов последовательности: min := 2001; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i]+a[j]) mod 2 = 1) and (a[i]+a[j] < min) then min := a[i]+a[j]; end end;	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может отсутствовать или быть представленной отдельными фрагментами, без ограничений на количество ошибок.	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4

Решение · Критерии · Помощь

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