РЕШУ ЕГЭ — информатика

Задания

Датчик передаёт каждую секунду по каналу связи неотрицательное целое число, не превосходящее 1000  — текущий результат измерений. Временем, в течение которого происходит передача, можно пренебречь.

Необходимо найти в заданной серии показаний датчика минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 15 секунд. Если получить такое произведение не удаётся, ответ считается равным -1. Общее количество показаний датчика в серии не превышает 10 000.

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

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

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

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

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

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

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

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

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

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

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

110

120

130

140

150

160

Программа должна вывести одно число  — описанное в условии произведение, либо −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;

    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;

}

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

Критерии оценивания выполнения задания	Баллы
Критерии оценивания задания А
Программа решает поставленную задачу для любых соответствующих условию входных данных. Например, допускается переборное решение, аналогичное приведённой выше Программе 1. Допускается до семи синтаксических и приравненных к ним ошибок (см. критерии оценивания задания Б на 4 балла). Допускается до двух содержательных ошибок, описанныхв критериях оценивания задания Б на 3 балла	2
Не выполнены условия, позволяющие поставить 2 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. 1 балл ставится также за решения, верные лишь в частных случаях	1
Не выполнены критерии, позволяющие поставить 1 или 2 балла	0
Максимальный балл для задания А	2

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

Ключ