Присоединиться

Информатика·Задания Д27 C4. Программирование·11 класс

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

Условие

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.Описание входных и выходных данных.В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.Пример входных данных:53412515251Пример выходных данных для приведённого выше примера входных данных:51 51 Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (34, 12), (34, 52), (51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды.Требуется написать эффективную по времени и памяти программу для решения описанной задачи.Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз.Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, — 4 балла. Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m, — 3 балла.Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию. Критерии оценивания выполнения задания | Баллы | Программа правильно работает для любых входных данных произвольного размера при условии исправления в ней не более трёх синтаксических ошибок из приведённого ниже списка допустимых ошибок. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству.Допускается наличие в тексте программы до трёх синтаксическихошибок одного из следующих видов:1) пропущен или неверно указан знак пунктуации;2) неверно написано, пропущено или написано лишнеезарезервированное слово языка программирования;3) не описана или неверно описана переменная;4) применяется операция, не допустимая для соответствующего типа данных.Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку. | 4 | Не выполнены условия, позволяющие поставить 4 балла.Программа работает правильно для любых входных данных произвольного размера при условии исправления в ней не более пяти синтаксических ошибок из приведённого в критериях на 4 балла списка и не более одной ошибки из приведённого ниже списка содержательных ошибок. Время работы пропорционально количеству введённых чисел, но может существенно зависеть от m(см. комментарий к эффективному решению задачи). Допускается наличие не более одной содержательной ошибки следующих видов:1) допущена ошибка при вводе данных (например, несчитывается значение N, или числа могут быть считаны, только если будут записаны в одной строке через пробел);2) неверная инициализация или её отсутствие там, где она необходима;3) используется неверный тип данных, при этом ошибка не является синтаксической;4) не более одного раза используется одна переменная (или константа) вместо другой, или не более одного раза используется один знак операции вместо другого, или не более одного раза используется одно зарезервированное слово языка программирования вместо другого, при этом ошибка не является синтаксической;5) служебное слово else относится не к тому if, к какому следует;6) отсутствует вывод ответа, или выводится значение не тех переменных;7) выход за границу массива (в частности, при обращении к m-му элементу массива с индексами от 0 до m-1, даже если он существует, но не заполнен нужным значением);8) не выполнен или неверно выполнен учёт элементов, остаток от деления которых на m равен 0.3 балла также ставится за программу, в которой нетсодержательных ошибок, но используемая память зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных). | 3 | Не выполнены условия, позволяющие поставить 3 или 4 балла.Программа работает верно, эффективно по времени при условии исправления не более трёх содержательных ошибок, описанных в критериях на 3 балла и аналогичных им, и не более девяти синтаксических ошибок, указанных в критериях на 4 балла. При этом в программе могут быть опущены с помощью многоточия однотипные действия, связанные с рассмотрением каждого из остатков от деления на m. Не допускается выставление 2 баллов за программу, если в ней учитываются суммы вида a[i]+a[i] (в том числе в алгоритме без хранения элементов последовательности).2 балла также ставится за корректное переборное решение, в котором все числа сохраняются в массиве (или другой аналогичной структуре) и рассматриваются все возможные пары. Пример фрагмента соответствующей программы на языке Паскаль:left := 0; right := 0;for i := 1 to N - 1 dofor j := i + 1 to N doif (a[i] > a[j]) and ((a[i] + a[j]) mod m = 0) thenif a[i] + a[j] > left + right thenbeginleft := a[i];right := a[j]end;В цикле реализации переборного алгоритма не допускаются выход индексов за границы массива, а также любые логические ошибки | 2 | Не выполнены условия, позволяющие поставить 2, 3 или 4 балла.При этом программа описывает в целом правильный алгоритм (эффективный или нет) и в ней присутствует не менее двух элементов решения из перечисленных ниже, возможно, реализованных с ошибками:• учитывается условие a[i] > a[j];• проверяется делимость суммы на m;• ищется пара с максимальной суммой.В случае, если в любом решении содержится не более одного из указанных элементов, программа оценивается в 0 баллов. | 1 | Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла. | 0 | Максимальный балл | 4 |

Формат задания

Развёрнутый ответ: короткого ответа здесь нет — оценивается само рассуждение. Ниже разбор по шагам.

Решение по шагам

  1. Как рассуждать

    Программа на языке Паскаль. Программа эффективна по времени и памяти. var N: integer; a: integer; i: integer; max: array [0..1] of integer; max17: array [0..1] of integer;begin max[0] := 0; max[1] := 0; max17[0] := 0; max17[1] := 0; readln(N); for i := 1 to N do begin readln(a); if (a mod 17 =

Осталось ещё 6 шагов — откроются после входа:

  • Шаг 2
  • Шаг 3
  • Шаг 4
  • Шаг 5
  • Шаг 6
  • Шаг 7
Получить полное решение

Бесплатно · займёт минуту

Другие задачи по теме «Задания Д27 C4. Программирование»