Дана последовательность целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше друг от друга (разница в индексах элементов должна быть или более). Необходимо определить максимальную сумму такой пары.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел . В каждой из последующих строк записано одно натуральное число, не превышающее .
Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
Пояснение. Из чисел можно составить пары, удовлетворяющие условию. Это будут элементы с индексами и , и , и . Для заданного набора чисел получаем пары , , . Максимальная сумма чисел в этих парах равна .
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел в раз время работы программы увеличивается не более чем в раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает килобайта и не увеличивается с ростом .
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Показать разбор
Содержание верного ответа (допускаются иные формулировки ответа, не искажающие его смысла)
Правильная и эффективная программа (использован циклический массив)
const s=8; {требуемое расстояние между элементами}
var
N: integer; {количество чисел}
x: integer; {очередное число}
a: array[0..s-1] of integer;
m: integer; {максимальное число}
sm: integer; {максимальная сумма пары}
i: integer; {счётчик для ввода}
ia: integer; {текущий индекс в массиве a}
begin
readln(N);
{ввод первых s чисел}
for i:=0 to s-1 do readln(a[i]);
{ввод и обработка остальных значений}
m:=0; sm:=0; ia:=0;
for i:=s to N-1 do begin
readln(x);
if a[ia] > m then m := a[ia];
if m+x > sm then sm := m+x;
a[ia] := x;
ia := (ia+1) mod s
end;
writeln(sm)
end.
Будем рассматривать каждое введённое число как правый элемент возможной пары (первые чисел не могут быть такими элементами). Для получения максимальной суммы нужно сложить это число с максимальным из всех элементов, расположенных от начала последовательности до элемента, расположенного на позиций раньше текущего. Будем хранить этот максимум и корректировать его при вводе каждого нового элемента. Для этого понадобится хранить последние элементов. Остальные элементы последовательности можно не хранить, это обеспечивает эффективность по памяти. Для хранения элементов можно использовать циклический массив, как показано в решении .
Вместо циклического массива можно использовать сдвиги. В этом случае для вычисления максимума всегда используется первый элемент массива, а новое число записывается в последний. Хотя этот алгоритм работает медленнее, чем алгоритм с циклическим массивом (для каждого элемента требуется дополнительных присваиваний при сдвигах), основное требование эффективности здесь выполнено: при увеличении размера массива в раз количество действий растёт не более чем в раз. В решении приводится пример такой программы.
Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и выберем из них требуемую. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Такая программа оценивается не выше двух баллов.
В решении приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC).
Указания по оцениванию
Баллы
Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бόльшая из двух оценок. Описание алгоритма решения без программы оценивается в баллов.
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов: 1) поставлен лишний, пропущен или неверно указан знак пунктуации; 2) написано лишнее, пропущено или неверно написано служебное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, недопустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку.
Не выполнены условия, позволяющие поставить балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных). Количество синтаксических ошибок («описок»), указанных в критериях на балла, – не более пяти. Допускается наличие не более одной ошибки следующих видов: 1) ошибка при вводе данных (не считывается значение или неверно организован ввод последовательности); 2) ошибка при инициализации или отсутствие инициализации там, где она необходима; 3) используется неверный тип данных; 4) использована одна переменная (константа) вместо другой; 5) используется один знак операции вместо другого; 6) отсутствует вывод ответа или выводится не то значение (хотя правильный ответ в программе найден); 7) неверная работа с массивом, в том числе выход за границы массива; 8) пропущены или неверно расставлены операторные скобки (при использовании языков с операторными скобками).
Не выполнены условия, позволяющие поставить или балла, при этом программа работает в целом верно и эффективно по времени. Допускается наличие до трёх содержательных ошибок, описанных в критериях на балла, и до девяти синтаксических ошибок, описанных в критериях на балла. балла также ставится за корректные переборные решения, в которых все исходные данные сохраняются в массиве (или другой аналогичной структуре) и рассматриваются все возможные пары. При этом не допускаются содержательные логические ошибки, например, выход индексов за границы массива, неверный учёт расстояния между элементами и т. д.
Не выполнены условия, позволяющие поставить , или балла. При этом программа представлена и содержит как минимум два обязательных элемента, возможно, реализованных с ошибками: 1) рассматриваются только пары, находящиеся на расстоянии не меньше заданного в условии; 2) сумма элементов пары сравнивается с максимумом.
Не выполнены условия, позволяющие поставить , , или балла.
Максимальный балл
Это задание составили эксперты «СтатГрада» для Яндекса
целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 
друг от друга (разница в индексах элементов должна быть 
. В каждой из последующих 
.
и 
, 
, 
. Максимальная сумма чисел в этих парах равна 
раз время работы программы увеличивается не более чем в 