Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 6 (разница в индексах элементов должна быть 6 или более). Необходимо определить максимальную нечётную сумму такой пары. Если пар с нечётной суммой нет, ответ считается равным 0.
Описание входных и выходных данных.
В первой строке входных данных задаётся количество чисел N (6 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
8
1
3
5
4
6
7
9
8
Пример выходных данных для приведённого выше примера входных данных:
11
Пояснение. Из восьми чисел можно составить три пары, удовлетворяющие условию. Это будут элементы с индексами 1 и 7, 1 и 8, 2 и 8. Для заданного набора чисел получаем пары (1, 9), (1, 8), (3, 8). Суммы чисел в этих парах равны 10, 9, 11. Нечётных сумм — две, максимальная из них равна 11.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Описание входных и выходных данных.
В первой строке входных данных задаётся количество чисел N (6 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
8
1
3
5
4
6
7
9
8
Пример выходных данных для приведённого выше примера входных данных:
11
Пояснение. Из восьми чисел можно составить три пары, удовлетворяющие условию. Это будут элементы с индексами 1 и 7, 1 и 8, 2 и 8. Для заданного набора чисел получаем пары (1, 9), (1, 8), (3, 8). Суммы чисел в этих парах равны 10, 9, 11. Нечётных сумм — две, максимальная из них равна 11.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
💡 Пошаговый разбор и решение:
Сумма двух чисел нечётна, если эти числа имеют разную чётность.
Будем хранить отдельно максимальные чётный и нечётный элементы последовательности без учёта шести последних элементов. Для этого понадобится хранить последние шесть элементов. Остальные элементы последовательности можно не хранить, это обеспечивает эффективность по памяти. Для хранения шести элементов можно использовать циклический массив, как показано в решении 1.
Будем рассматривать каждое введённое число как правый элемент возможной пары (первые шесть чисел не могут быть таким элементом), в зависимости от его чётности определять максимально возможную сумму такой пары и сравнивать её с общим максимумом. При этом важно убедиться, что максимальный элемент нужной чётности существует, и не вычислять сумму текущего элемента с нулём
Решение 1. Правильная и эффективная программы на языке Паскаль (использован циклический массив):
const d=6; {требуемое расстояние между элементами}
var
N: integer; {количество чисел}
x: integer; {очередное число}
a: array[0..d-1] of integer;
m0,m1 : integer; {чётный и нечётный максимумы}
s: integer; {максимальная сумма с текущим элементом}
msum: integer; {максимальная нечётная сумма пары}
i: integer; {счётчик для ввода}
ia: integer; {текущий индекс в массиве a}
begin
readln(N);
{ввод первых d чисел}
for i:=0 to d-1 do readln(a[i]);
{ввод и обработка остальных значений}
m0:=0; m1:=0; msum := 0;
ia:=0;
for i:=d to N-1 do begin
readln(x);
if (a[ia] mod 2 = 0) and (a[ia] > m0) then m0 := a[ia];
if (a[ia] mod 2 = 1) and (a[ia] > m1) then m1 := a[ia];
s:=0;
if (x mod 2 = 0) and (m1 > 0) then s := x + m1;
if (x mod 2 = 1) and (m0 > 0) then s := x + m0;
if s > msum then msum := s;
a[ia] := x;
ia := (ia+1) mod d
end;
writeln(msum)
end.
Вместо циклического массива можно использовать сдвиги. В этом случае для вычисления всегда используется первый элемент массива, а новое число записывается в последний. Хотя этот алгоритм работает медленнее, чем алгоритм с циклическим массивом (для каждого элемента требуется пять дополнительных присваиваний при сдвигах), основное требование эффективности здесь выполнено: при увеличении размера массива в k раз количество действий растёт не более чем в k раз. Ниже приводится пример такой программы.
Решение 2. Правильная и эффективная программы на языке Паскаль (использован сдвиг массива)
const d=6; {требуемое расстояние между элементами}
var
N: integer; {количество чисел}
x: integer; {очередное число}
a: array[1..d] of integer;
m0,m1 : integer; {чётный и нечётный максимумы}
s: integer; {максимальная сумма с текущим элементом}
msum: integer; {максимальная нечётная сумма пары}
i: integer; {счётчик для ввода}
ia: integer; {счётчик для сдвига}
begin
readln(N);
{ввод первых d чисел}
for i:=1 to d do readln(a[i]);
{ввод и обработка остальных значений}
m0:=0; m1:=0; msum := 0;
for i:=d+1 to N do begin
readln(x);
if (a[1] mod 2 = 0) and (a[1] > m0) then m0 := a[1];
if (a[1] mod 2 = 1) and (a[1] > m1) then m1 := a[1];
s:=0;
if (x mod 2 = 0) and (m1 > 0) then s := x + m1;
if (x mod 2 = 1) and (m0 > 0) then s := x + m0;
if s > msum then msum := s;
for ia:=1 to d-1 do a[ia]:=a[ia+1];
a[s] := x;
end;
writeln(msum)
end.
Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и определим требуемую сумму. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Такая программа оценивается не выше 2 баллов.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)
Решение 3. Правильная, но неэффективная программы на языке Паскаль:
const d=6; {требуемое расстояние между элементами}
var
N: integer; {количество чисел}
a: array [1..1000] of integer; {исходные данные}
s: integer; {сумма пары}
msum: integer; {максимальная нечётная сумма пары}
i,j: integer;
begin
readln(N);
for i:=1 to N do readln(a[i]);
msum :=0;
for i := 1 to N-d do begin
for j := i+d to N do begin
s := a[i] + a[j];
if (s mod 2 = 1) and (s > msum)
then msum := s
end
end;
writeln(msum)
end.
Будем хранить отдельно максимальные чётный и нечётный элементы последовательности без учёта шести последних элементов. Для этого понадобится хранить последние шесть элементов. Остальные элементы последовательности можно не хранить, это обеспечивает эффективность по памяти. Для хранения шести элементов можно использовать циклический массив, как показано в решении 1.
Будем рассматривать каждое введённое число как правый элемент возможной пары (первые шесть чисел не могут быть таким элементом), в зависимости от его чётности определять максимально возможную сумму такой пары и сравнивать её с общим максимумом. При этом важно убедиться, что максимальный элемент нужной чётности существует, и не вычислять сумму текущего элемента с нулём
Решение 1. Правильная и эффективная программы на языке Паскаль (использован циклический массив):
const d=6; {требуемое расстояние между элементами}
var
N: integer; {количество чисел}
x: integer; {очередное число}
a: array[0..d-1] of integer;
m0,m1 : integer; {чётный и нечётный максимумы}
s: integer; {максимальная сумма с текущим элементом}
msum: integer; {максимальная нечётная сумма пары}
i: integer; {счётчик для ввода}
ia: integer; {текущий индекс в массиве a}
begin
readln(N);
{ввод первых d чисел}
for i:=0 to d-1 do readln(a[i]);
{ввод и обработка остальных значений}
m0:=0; m1:=0; msum := 0;
ia:=0;
for i:=d to N-1 do begin
readln(x);
if (a[ia] mod 2 = 0) and (a[ia] > m0) then m0 := a[ia];
if (a[ia] mod 2 = 1) and (a[ia] > m1) then m1 := a[ia];
s:=0;
if (x mod 2 = 0) and (m1 > 0) then s := x + m1;
if (x mod 2 = 1) and (m0 > 0) then s := x + m0;
if s > msum then msum := s;
a[ia] := x;
ia := (ia+1) mod d
end;
writeln(msum)
end.
Вместо циклического массива можно использовать сдвиги. В этом случае для вычисления всегда используется первый элемент массива, а новое число записывается в последний. Хотя этот алгоритм работает медленнее, чем алгоритм с циклическим массивом (для каждого элемента требуется пять дополнительных присваиваний при сдвигах), основное требование эффективности здесь выполнено: при увеличении размера массива в k раз количество действий растёт не более чем в k раз. Ниже приводится пример такой программы.
Решение 2. Правильная и эффективная программы на языке Паскаль (использован сдвиг массива)
const d=6; {требуемое расстояние между элементами}
var
N: integer; {количество чисел}
x: integer; {очередное число}
a: array[1..d] of integer;
m0,m1 : integer; {чётный и нечётный максимумы}
s: integer; {максимальная сумма с текущим элементом}
msum: integer; {максимальная нечётная сумма пары}
i: integer; {счётчик для ввода}
ia: integer; {счётчик для сдвига}
begin
readln(N);
{ввод первых d чисел}
for i:=1 to d do readln(a[i]);
{ввод и обработка остальных значений}
m0:=0; m1:=0; msum := 0;
for i:=d+1 to N do begin
readln(x);
if (a[1] mod 2 = 0) and (a[1] > m0) then m0 := a[1];
if (a[1] mod 2 = 1) and (a[1] > m1) then m1 := a[1];
s:=0;
if (x mod 2 = 0) and (m1 > 0) then s := x + m1;
if (x mod 2 = 1) and (m0 > 0) then s := x + m0;
if s > msum then msum := s;
for ia:=1 to d-1 do a[ia]:=a[ia+1];
a[s] := x;
end;
writeln(msum)
end.
Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и определим требуемую сумму. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Такая программа оценивается не выше 2 баллов.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)
Решение 3. Правильная, но неэффективная программы на языке Паскаль:
const d=6; {требуемое расстояние между элементами}
var
N: integer; {количество чисел}
a: array [1..1000] of integer; {исходные данные}
s: integer; {сумма пары}
msum: integer; {максимальная нечётная сумма пары}
i,j: integer;
begin
readln(N);
for i:=1 to N do readln(a[i]);
msum :=0;
for i := 1 to N-d do begin
for j := i+d to N do begin
s := a[i] + a[j];
if (s mod 2 = 1) and (s > msum)
then msum := s
end
end;
writeln(msum)
end.
📚 Похожие разобранные задания по предмету:
ID 140782 • Задание №14
В электронную таблицу занесли данные о тестировании учеников. Ниже приведены первые пять строк таблицы.
| A |...
ID 29873 • Задание №4
Для кодирования букв О, К, Г, Д, Р решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответстве...
Официальные критерии проверки ФИПИ:
Критерии проверки:
Критерии оценивания выполнения задания | Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству.
Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов:
1) пропущен или неверно указан знак пунктуации,
2) неверно написано или пропущено зарезервированное слово языка программирования,
3) не описана или неверно описана переменная,
4) применяется операция, недопустимая для соответствующего типа данных.
Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку. | 4
Не выполнены условия, позволяющие поставить 4 балла.
Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины
должны вычисляться по ходу чтения элементов последовательности чисел.
Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных).
Количество синтаксических ошибок («описок»), указанных в критериях на 4 балла, — не более пяти.
Допускается наличие не более одной ошибки следующих видов:
1) ошибка при вводе данных (не считывается значение N или неверно организован ввод последовательности);
2) ошибка при инициализации или отсутствие инициализации там, где она необходима;
3) используется неверный тип данных;
4) использована одна переменная (константа) вместо другой;
5) используется один знак операции вместо другого;
6) отсутствует вывод ответа или выводится не то значение (хотя правильный ответ в программе найден);
7) неверная работа с массивом, в том числе выход за границы массива;
8) пропущены или неверно расставлены операторные скобки (при использовании языков с операторными скобками). | 3
Не выполнены условия, позволяющие поставить 3 или 4 балла, при этом программа работает в целом верно и эффективно по времени. Допускается наличие до трёх содержательных ошибок, описанных в критериях на 3 балла, и до девяти синтаксических ошибок, описанных в критериях на 4 балла.
2 балла также ставится за корректные переборные решения, в которых все исходные данные сохраняются в массиве (или другой аналогичной структуре) и рассматриваются все возможные пары. При этом не допускаются содержательные логические ошибки, например, выход индексов за границы массива, неверный учёт расстояния между элементами и т.д. | 2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла.
При этом программа представлена и содержит как минимум два обязательных элемента, возможно, реализованных с ошибками:
1) рассматриваются только пары, находящиеся на расстоянии не меньше заданного в условии;
2) определяется пара с максимальная нечётной суммой. | 1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла | 0
Максимальный балл | 4
Критерии оценивания выполнения задания | Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству.
Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов:
1) пропущен или неверно указан знак пунктуации,
2) неверно написано или пропущено зарезервированное слово языка программирования,
3) не описана или неверно описана переменная,
4) применяется операция, недопустимая для соответствующего типа данных.
Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку. | 4
Не выполнены условия, позволяющие поставить 4 балла.
Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины
должны вычисляться по ходу чтения элементов последовательности чисел.
Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных).
Количество синтаксических ошибок («описок»), указанных в критериях на 4 балла, — не более пяти.
Допускается наличие не более одной ошибки следующих видов:
1) ошибка при вводе данных (не считывается значение N или неверно организован ввод последовательности);
2) ошибка при инициализации или отсутствие инициализации там, где она необходима;
3) используется неверный тип данных;
4) использована одна переменная (константа) вместо другой;
5) используется один знак операции вместо другого;
6) отсутствует вывод ответа или выводится не то значение (хотя правильный ответ в программе найден);
7) неверная работа с массивом, в том числе выход за границы массива;
8) пропущены или неверно расставлены операторные скобки (при использовании языков с операторными скобками). | 3
Не выполнены условия, позволяющие поставить 3 или 4 балла, при этом программа работает в целом верно и эффективно по времени. Допускается наличие до трёх содержательных ошибок, описанных в критериях на 3 балла, и до девяти синтаксических ошибок, описанных в критериях на 4 балла.
2 балла также ставится за корректные переборные решения, в которых все исходные данные сохраняются в массиве (или другой аналогичной структуре) и рассматриваются все возможные пары. При этом не допускаются содержательные логические ошибки, например, выход индексов за границы массива, неверный учёт расстояния между элементами и т.д. | 2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла.
При этом программа представлена и содержит как минимум два обязательных элемента, возможно, реализованных с ошибками:
1) рассматриваются только пары, находящиеся на расстоянии не меньше заданного в условии;
2) определяется пара с максимальная нечётной суммой. | 1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла | 0
Максимальный балл | 4
🔗 Другие задания линии №27 по предмету Информатика:
ID 34669
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой ...
ID 34670
Последовательность натуральных чисел характеризуется числом Х — наибольшим числом, кратным 14 ...
ID 34671
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются ...
ID 34672
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последо...
ID 34673
На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары...