260 подписчиков

ЕГЭ по информатике. Задание 27

4 минуты

101 прочтение

18 мая 2020

Задание 27 — «Обработка строк или последовательности чисел». Это задание характеризуется высоким уровнем сложности, время выполнения – 50 минут, максимальный балл — 4.

Конечно, это как-то нечестно, писать сложную программу без возможности ее проверить на компьютере.

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

Рассмотрим пример:

На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a[i] и a[j] такие что i < j и a[i] > a[j] (первый элемент пары больше второго; i и j – порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел n (2<=n<=12000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10000. В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.

Пример входных данных
6
60
140
61
100
300
59

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

Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m = 120: 60+300, 140+100 и 61+59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

Решение.(привожу на Паскале)

Сумма a[i] и a[j] делится на m, если сумма остатков этих чисел от деления на m равна 0 или m. Для каждого из остатков от деления на m среди уже просмотренных элементов будем хранить максимальное число, имеющее соответствующий остаток от деления на m. Для этого будем использовать массив s длиной m изначально с элементами, равными 0. Все считанные значения при этом можно не хранить.

Очередное считанное число a будем рассматривать как возможный правый элемент искомой пары. Пусть остаток от деления a на m равен p. Тогда если s[m - p] > 0 то сумма a и s[m - p] делится на m и при условии s[m - p]>a эта пара – вариант для ответа. Если их сумма больше предыдущего ответа, то заменим его. При этом если остаток от деления a на m равен 0, то рассматривать надо пару a и s[0].

По окончании обработки элемента a необходимо обновить элемент s[p] значением a, если a > s[p].

const m = 120;
var
s: array[0..m-1] of integer;
n, a, i, p, left, right: integer;
begin
readln(n);
for i := 0 to m - 1 do
s[i] := 0; {обнуление массива}
left := 0; right := 0; {обнуление переменных для записи ответа}
for i := 1 to n do
begin
readln(a); {считываем очередное значение}
p := a mod m; {находим остаток}
if p = 0 then
begin
if (s[0] > a) and (s[0] + a > left + right) then
begin
left := s[0]; right := a {обновление ответа}
end
end
else
begin
if (s[m - p] > a) and (s[m - p] + a > left + right) then
begin
left := s[m - p]; right := a {обновление ответа}
end;
end;
if a > s[p] then s[p] := a {обновление элемента для остатка}
end;
writeln(left, ' ',right)
end.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.

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

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

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

Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m, - 3 балла.

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

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

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

Описание алгоритма решения без программы оценивается в 0 баллов.

Если остались вопросы, пишите в комментариях. Обязательно отвечу. Если нужно разобрать конкретный пример, также - в комментарии.