СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
Информатика
Cайты, меню, вход, новости


Задания
Версия для печати и копирования в MS Word
Задания Д27 C4 № 8115

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

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

 

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

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

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

 

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

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

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

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

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

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

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

 

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

 

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

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

11

12

45

5

3

17

23

21

20

19

12

26

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

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

95

Решение.

Задание А.

Считаем все числа. После чего пробежимся по полученному массиву и для данной позиции посмотрим на все числа, стоящие на 6 дальше него, посчитаем их произведение. Таким образом мы переберём все возможные произведения пар и выберем из них минимум.

 

Код на языке Pascal:

 

var n, i, j : integer;

     mul, ans : longint;

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

begin

readln(n);

for i := 1 to n do

     readln(a[i]);

ans := -1;

for i := 1 to n - 6 do

     for j := i + 6 to n do

         begin

         mul := a[i] * a[j];

         if (mul mod 2 = 1) and ((ans = -1) or (mul < ans)) then

             ans := mul;

         end;

writeln(ans);

end.

 

      Задание Б.

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

 

Код на языке Pascal:

 

const step = 6;

var n, i : integer;

     min, ans : longint;

     buf : array [0 .. step - 1] of integer;

begin

readln(n);

for i := 0 to step - 1 do

     readln(buf[i]);

ans := -1;

min := -1;

for i := step to n - 1 do

     begin

     if (buf[i mod step] mod 2 = 1) and ((min = -1) or (buf[i mod step] < min)) then

         min := buf[i mod step];

     readln(buf[i mod step]);

     if (min <> -1) and (buf[i mod step] mod 2 = 1) and ((ans = -1) or (min * buf[i mod step] < ans)) then

         ans := min * buf[i mod step];

     end;

writeln(ans);

end.

 

Небольшие пояснения к коду.

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

Фрагмент в начале каждой итерации используется как позиция в массиве на 6 раньше текущей. Используется для пересчёта текущего минимума. После чего в эту же ячейку считывается число на текущей позиции и уже используется для пересчёта ответа.

 

Приведём решение Владимира Бабий (Челябинск), Информатик БУ.

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

n = int(input())

a = []

mx = 10 ** 9

m = 10 ** 9

for i in range(6):

    a.append(int(input()))

for i in range(6, n):

    x = int(input())

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

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

    a[i % 6] = x

print(m)


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

Источник: ЕГЭ 05.05.2015. Досрочная волна.
Спрятать решение · Прототип задания · · Курс 80 баллов ·
Гость 15.06.2015 07:21

begin

if (buf[i mod step] mod 2 = 1) and ((min = -1) or (buf[i mod step] < min)) then

min := buf[i mod step];

readln(buf[i mod step]);

if (min <> -1) and (buf[i mod step] mod 2 = 1) and ((ans = -1) or (min * buf[i mod step] < ans)) then

ans := min * buf[i mod step];

end;

Вероятно, readln(buf[i mod step]); должно занимать 2, а не 4 строку кода

Никита Горохов

Нет. В пояснении написано об этом. Во второй строке эта ячейка используется в качестве позиции, которая идёт на 6 раньше, и нужна для пересчёта минимума. В четвёртой же строчке эта ячейка используется уже как текущая позиция в массиве и нужна для считывание значения в текущей позиции.