На вход программы поступает последовательность из n целых положительных чисел рассматриваются
На вход программы поступает последовательность из целых положительных чисел. Рассматриваются все пары элементов последовательности и такие что и (первый элемент пары больше второго; и – порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел В каждой из последующих строк записано одно целое положительное число, не превышающее
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Пример входных данных
Пример выходных данных для приведённого выше примера входных данных:
Разбор задания 27 из ДЕМОВЕРСИИ 2020 ЕГЭ по информатике
Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на и Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности и параметра в раз время работы программы увеличивается не более чем в раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает килобайта и не увеличивается с ростом .
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, балла.
Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Показать разбор
(допускаются иные формулировки ответа, не искажающие его смысла)
Сумма и делится на если сумма остатков этих чисел от деления на равна или Для каждого из остатков от деления на среди уже просмотренных элементов будем хранить максимальное число, имеющее соответствующий остаток от деления на Для этого будем использовать массив длиной изначально с элементами, равными Все считанные значения при этом можно не хранить.
27 задание ЕГЭ Информатика Определение количества троек
Очередное считанное число будем рассматривать как возможный правый элемент искомой пары. Пусть остаток от деления на равен Тогда если то сумма и делится на и при условии эта пара – кандидат для ответа. Если их сумма больше предыдущего ответа, то заменим его. При этом если остаток от деления на равен то рассматривать надо пару и
По окончании обработки элемента необходимо обновить элемент значением если
Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия 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; # обновление элемента r для соответствующего остатка 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; //обнуление массива r 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; //обновление ответа > // обновление элемента r для соответствующего остатка if (p < m) < if (a > r[p]) r[p] = a; > else if (a > r[0]) r[0] = a; > cout ‘ ‘
Указания по оцениванию
Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бо́льшая из двух оценок. Описание алгоритма решения без программы оценивается в баллов
Порядок назначения третьего эксперта
В соответствии с Порядком проведения государственной итоговой аттестации по образовательным программам среднего общего образования (приказ Минпросвещения России и Рособрнадзора от зарегистрирован Минюстом России ).
« По результатам первой и второй проверок эксперты независимо друг от друга выставляют баллы за каждый ответ на задания экзаменационной работы ЕГЭ с развернутым ответом.
случае существенного расхождения в баллах, выставленных двумя экспертами, назначается третья проверка. Существенное расхождение в баллах определено в критериях оценивания по соответствующему учебному предмету.
Эксперту, осуществляющему третью проверку, предоставляется информация о баллах, выставленных экспертами, ранее проверявшими экзаменационную работу».
Если расхождение составляет или более балла за выполнение задания, то третий эксперт проверяет только те ответы, которые вызвали столь существенное расхождение.
Критерии оценки
Указания по оцениванию и баллы
4 балла Программа правильно работает для любых входных данных произвольного размера при условии исправления в ней не более трёх синтаксических ошибок из приведённого ниже списка допустимых ошибок. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству.
Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов:
1. пропущен или неверно указан знак пунктуации;
2. неверно написано, пропущено или написано лишнее зарезервированное слово языка программирования;
3. не описана или неверно описана переменная;
4. применяется операция, не допустимая для соответствующего типа данных.
Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку
3 балла Не выполнены условия, позволяющие поставить балла.
Программа работает правильно для любых входных данных произвольного размера при условии исправления в ней не более пяти синтаксических ошибок из приведённого в критериях на балла списка и не более одной ошибки из приведённого ниже списка содержательных ошибок. Время работы пропорционально количеству введённых чисел, но может существенно зависеть от (см. комментарий к эффективному решению задачи). Допускается наличие не более одной содержательной ошибки следующих видов:
1. допущена ошибка при вводе данных (например, не считывается значение или числа могут быть считаны, только если будут записаны в одной строке через пробел);
2. неверная инициализация или её отсутствие там, где она необходима;
3. используется неверный тип данных, при этом ошибка не является синтаксической;
4. не более одного раза используется одна переменная (или константа) вместо другой, или не более одного раза используется один знак операции вместо другого, или не более одного раза используется одно зарезервированное слово языка программирования вместо другого, при этом ошибка не является синтаксической;
5. служебное слово else относится не к тому if, к какому следует;
6. отсутствует вывод ответа, или выводится значение не тех переменных;
7. выход за границу массива (в частности, при обращении к -му элементу массива с индексами от до даже если он существует, но не заполнен нужным значением);
8. не выполнен или неверно выполнен учёт элементов, остаток от деления которых на равен
балла также ставится за программу, в которой нет содержательных ошибок, но используемая память зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных)
2 балла Не выполнены условия, позволяющие поставить или балла.
Программа работает верно, эффективно по времени при условии исправления не более трёх содержательных ошибок, описанных в критериях на балла и аналогичных им, и не более девяти синтаксических ошибок, указанных в критериях на балла. При этом в программе могут быть опущены с помощью многоточия однотипные действия, связанные с рассмотрением каждого из остатков от деления на
Не допускается выставление баллов за программу, если в ней учитываются суммы вида (в том числе в алгоритме без хранения элементов последовательности).
балла также ставится за корректное переборное решение, в котором все числа сохраняются в массиве (или другой аналогичной структуре) и рассматриваются все возможные пары. Пример фрагмента соответствующей программы на языке Паскаль:
left := 0; right := 0;
for i := 1 to N — 1 do
for j := i + 1 to N do
if (a[i] > a[j]) and ((a[i] + a[j]) mod m = 0) then
if a[i] + a[j] > left + right then
begin
left := a[i];
right := a[j]
end;
В цикле реализации переборного алгоритма не допускаются выход индексов за границы массива, а также любые логические ошибки
1 балл Не выполнены условия, позволяющие поставить или балла.
При этом программа описывает в целом правильный алгоритм (эффективный или нет) и в ней присутствует не менее двух элементов решения из перечисленных ниже, возможно, реализованных с ошибками:
— учитывается условие
— проверяется делимость суммы на
— ищется пара с максимальной суммой.
В случае, если в любом решении содержится не более одного из указанных элементов, программа оценивается в баллов
Источник: yandex.ru
Линия заданий 27, ЕГЭ по информатике
19220. Имеется набор данных, состоящих из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6 1 3 5 12 6 9 5 4 3 3 1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Показать подсказку
Верный ответ: 583 662957374
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 19220.
19193. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6 1 3 5 12 6 9 5 4 3 3 1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Например 5 55
Показать подсказку
Верный ответ: 9671 747190
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 19193.
19166. Дана последовательность, которая состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел как в первой, так и во второй группе должна быть нечётной.
Определите максимально возможную сумму всех чисел в третьей группе.
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10000.
Пример входного файла:
3 1 3 8 9 12 4 7 11 10
Для указанных данных искомая сумма равна 31, она соответствует такому распределению чисел по группам: (1, 9, 7), (3, 4, 10), (8, 12, 11). В ответе укажите два числа: сначала искомое значение для файла A, затем для файла B.
Показать подсказку
Верный ответ: 2996 454694482
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 19166.
19139. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6 1 3 5 12 6 9 5 4 3 3 1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Например 5 55
Показать подсказку
Верный ответ: 9671 747190
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 19139.
19112. Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых четна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов.
Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 100002 ≤ N ≤ 10000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию:
(34, 12), (34, 52), (51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды.
Напишите, что выведет программа на входных данных из файла A и файла B.
Формат ответа (A и B — буквы латинского алфавита):
A — 123 123
B — 123 123
В каждой пары записывать числа по возрастанию
Показать подсказку
A — 0 0
B — 9928 9992
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 19112.
19085. На вход программы поступает последовательность из N целых положительных чисел.
Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом), такие что ai > aj при i aj, а i
Показать подсказку
A — 6379 8489
B — 9949 9959
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 19085.
19058. Имеется набор данных, состоящий из положительных целых чисел, каждое из которых не превышает 1000. Они представляют собой результаты измерений, выполняемых прибором с интервалом 1 минута. Требуется найти для этой последовательности контрольное значение – наименьшую сумму квадратов двух результатов измерений, выполненных с интервалом не менее, чем в 5 минут.
Входные данные: Даны два входных файла: файл A и файл B, каждый из которых содержит в первой строке количество чисел N (5 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1000.
Пример входного файла:
Для указанных данных искомое контрольное значение равно 169.
В ответе укажите два числа: сначала контрольное значение для файла А, затем для файла B.
Показать подсказку
Верный ответ: 11009 200
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 19058.
19031. В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны.
Из этой последовательности нужно выбрать четыре числа, чтобы их сумма делилась на 6 и была наибольшей. Какую наибольшую сумму можно при этом получить?
Входные данные: Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 5 ). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 5 .
Пример входного файла:
Для указанных данных можно выбрать четвёрки 4, 13, 11, 8 (сумма 36) и 13, 11, 10, 8 (сумма 42). Наибольшая из сумм – 42. В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла B.
Показать подсказку
Верный ответ: 348 399972
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 19031.
19004. В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны. Из этой последовательности нужно выбрать четыре числа, чтобы их сумма делилась на 9 и была наименьшей. Какую наименьшую сумму можно при этом получить?
Входные данные: Даны два входных файла: файл A и файл B, каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 8 .
Пример входного файла:
Для указанных данных можно выбрать четвёрки 5, 12, 2, 8 (сумма 27) и 12, 23, 2, 8 (сумма 45). Наименьшая из сумм – 27. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Показать подсказку
Верный ответ: 1332 406773
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 19004.
18977. Имеется набор данных, состоящий из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 13 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Показать подсказку
Верный ответ: 67089 200157480
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 18977.
Источник: studarium.ru