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

11 класс·высокий уровень

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

Условие

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, сумма которых делится на m = 60. Среди всех таких пар нужно найти и вывести пару с максимальным произведением элементов. Если одинаковое максимальное произведение имеют несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля. Описание входных и выходных данных.В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Гарантируется, что никакое число не встречается в последовательности более одного раза.

Пример входных данных:81030504060709080Пример выходных данных для приведённого выше примера входных данных:50 70Пояснение. Из данных восьми чисел можно составить четыре пары, удовлетворяющие условию: (10, 50), (30, 90), (50, 70), (40, 80). Наибольшее произведение получается в паре (50, 70).Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную только по времени — 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла. Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.

Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите используемый язык программирования и его версию. Пояснения для проверяющих.1. Задание Б является усложнением задания А. Если в качестве решения задания Б представлено решение задания А, то согласно приведённым ниже критериям, его оценка будет такой же, как если бы это решение было представлено в качестве решения задания А.2. Два задания и, соответственно, возможность для экзаменуемого представить две программы дают ученику возможность (при его желании) сначала написать менее сложное и менее эффективное решение (задание А), которое даёт ему право получить два балла, а затем приступить к поиску более эффективного решения. 3. Каждая из программ, представленных экзаменуемым (но не более двух), оценивается по нижеследующим критериям. В качестве итоговой оценки берётся наибольшая из двух оценок.

Ответ

Ответ и полный разбор откроются после входа

Посмотреть ответ

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

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

    Решение. Сумма двух чисел кратна m, если сумма остатков от деления этих чисел на m кратна m. При этом для получения максимального произведения из чисел с одинаковыми остатками нужно выбирать наибольшее. Будем хранить в массиве из m элементов максимальное число, имеющее соответствующий остаток от деления на m.Каждое введённое число будем рассматривать как правый элемент возможной пары, находить соответствующий ему парный остаток, вычислять произведение пары и при необходимости обновлять максимум для произведения и для чисел с данным остатком Пример

Осталось ещё 5 шагов

  1. Программа на языке Паскаль. Программа…

  2. В этом случае парный остаток тоже должен быть…

  3. Возможно вычисление pp с использованием…

  4. Правильная, но неэффективная программа на…

  5. and (a[i]*a[j] > x1*x2) then begin x1:=a[i]…

Получить полное решение

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

Другие задачи по теме «Программирование»

Укажите используемый язык программирования и его версию. — решение с объяснением | Lom Ai