Содержание верного ответа
(допускаются иные формулировки ответа, не искажающие его смысла)
Сумма и делится на если сумма остатков этих чисел от деления на равна или Для каждого из остатков от деления на среди уже просмотренных элементов будем хранить максимальное число, имеющее соответствующий остаток от деления на Для этого будем использовать массив длиной изначально с элементами, равными Все считанные значения при этом можно не хранить. Очередное считанное число будем рассматривать как возможный правый элемент искомой пары. Пусть остаток от деления на равен Тогда если то сумма и делится на и при условии эта пара – кандидат для ответа. Если их сумма больше предыдущего ответа, то заменим его. При этом если остаток от деления на равен то рассматривать надо пару и По окончании обработки элемента необходимо обновить элемент значением если Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC).
Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти
const m = 120;
var
r: array[0..m-1] of integer;
n, a, i, p, left, right: integer;
begin
readln(n);
for i := 0 to m - 1 do
r[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 (r[0] > a) and (r[0] + a > left + right) then
begin
left := r[0]; right := a
end
end
else
begin
if (r[m - p] > a) and (r[m - p] + a > left + right) then
begin
left := r[m - p]; right := a
end;
end;
if a > r[p] then r[p] := a
end;
writeln(left, ' ',right)
end.
Комментарии для проверяющего
1. При таком решении хранится только очередной прочитанный элемент и информация о максимальных значениях, имеющих различные остатки от деления на (на их хранение будет потрачено не более байт памяти, а на все переменные в целом – менее килобайт). Таким образом, используемая память не зависит от длины последовательности. Время обработки очередного числа фиксировано, т.е. не зависит от длины последовательности и даже от величины Поэтому при увеличении длины последовательности в раз время работы программы увеличивается не более чем в раз. Таким образом, приведённая выше программа эффективна как по времени, так и по используемой памяти. Это решение оценивается баллами. Программа может не рассматривать отдельно случай а учесть оба случая с помощью одной формулы: (m - p) mod m. Такой вариант реализации показан в примере программы на языке Python. Может быть реализовано решение с заменой на Такая программа на языке С++ приведена ниже (пример ). Все подобные программы оцениваются, исходя из максимального балла (см. критерии). 2. Возможно решение, основанное на описанных идеях, однако
предварительно сохраняющее элементы последовательности в массив или другие структуры данных. Такое решение эффективно по времени, но неэффективно по памяти. Оно оценивается, исходя из максимального балла (см. критерии). Кроме того, возможен неэффективный способ
определения, какой именно остаток от деления нас интересует, например с помощью цикла, выполняющегося до раз, или с помощью условных операторов: if p = 0 and a > r[0] then r[0] = a;
if p = 1 and a > r[1] then r[1] = a;
и т.д.
Такое решение работает в m раз дольше и оценивается, исходя из максимального балла (см. критерии). 3. Решение, неэффективное ни по времени, ни по памяти, запоминает входную последовательность в массиве, после чего явно перебирает все возможные пары. Такое решение оценивается, исходя из максимального балла (см. критерии). Пример 2. Программа на языке Python 3. Программа эффективна по времени и памяти
m = 120
r = [0] * m
left = 0
right = 0
n = int(input())
for i in range(n):
a = int(input())
p = a % m;
if r[(m - p) % m] > a and r[(m - p) % m] + a > left + right:
left = r[(m - p) % m]
right = a;
if a > r[p]:
r[p] = a
print(left, right)
Пример 3. Программа на языке С++. Программа эффективна по времени и памяти
#include <iostream>
using namespace std;
int main()
{
int n, a, p, left, right;
int r[120];
int m = 120;
cin >> n;
for (int i = 0; i < m; ++i)
r[i] = 0;
left = 0; right = 0;
for (int i = 0; i < n; ++i)
{
cin >> a;
p = a % m;
if (p == 0) p = m;
if (r[m - p] > a && r[m - p] + a > left + right)
{
left = r[m - p]; right = a;
}
if (p < m)
{
if (a > r[p]) r[p] = a;
}
else if (a > r[0]) r[0] = a;
}
cout << left << ' ' << right;
}
Указания по оцениванию
Если в работе представлены две программы решения задачи,
то каждая из них независимо оценивается по указанным ниже
критериям, итоговой считается бо́льшая из двух оценок. Описание алгоритма решения без программы оценивается в баллов Порядок назначения третьего эксперта
В соответствии с Порядком проведения государственной итоговой
аттестации по образовательным программам среднего общего образования
(приказ Минпросвещения России и Рособрнадзора от зарегистрирован Минюстом России ). « <…> По результатам первой и второй проверок эксперты
независимо друг от друга выставляют баллы за каждый ответ на задания
экзаменационной работы ЕГЭ с развернутым ответом. <…> случае существенного расхождения в баллах, выставленных двумя
экспертами, назначается третья проверка. Существенное расхождение в
баллах определено в критериях оценивания по соответствующему учебному
предмету.
Эксперту, осуществляющему третью проверку, предоставляется
информация о баллах, выставленных экспертами, ранее проверявшими
экзаменационную работу».
Если расхождение составляет или более балла за выполнение задания, то третий эксперт проверяет только те ответы,
которые вызвали столь существенное расхождение.