Задание №61644. На вход программы поступает последовательность из n целых

Задание №61644 ЕГЭ Информатике

Условие задания #61644

На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a_i и a_j, такие что i < j и a_i > a_j (первый элемент пары больше второго; i и j  — порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m  =  120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000).

В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.

В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.

Пример входных данных:

140

100

300

Пример выходных данных для приведённого выше примера входных данных:

140 100

Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m  =  120: 60 + 300, 140 + 100 и 61 + 59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.

Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти,  — 4 балла. Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m,  — 3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,  — 2 балла.

Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.

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

Ответ

Ответ:

Решение

Сумма a_i и a_j делится на m, если сумма остатков этих чисел от деления на m равна 0 или m. Для каждого из остатков от деления на m среди уже просмотренных элементов будем хранить максимальное число, имеющее соответствующий остаток от деления на m. Для этого будем использовать массив r длиной m, изначально с элементами, равными 0. Все считанные значения при этом можно не хранить.

Очередное считанное число a будем рассматривать как возможный правый элемент искомой пары. Пусть остаток от деления a на m равен p. Тогда если r[m–p] > 0, то сумма a и r[m–p] делится на m, и при условии r[m–p] > a эта пара  — кандидат для ответа. Если их сумма больше предыдущего ответа, то заменим его. При этом если остаток от деления a на m равен 0, то рассматривать надо пару a и r[0].

По окончании обработки элемента a необходимо обновить элемент r[p] значением a, если a > r[p].

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)

Понятно ли решение?

Авторизуйся, чтобы посмотреть решение

Активируй TG-бот через QR-код или по кнопке
Введи код авторизации из TG-бота

Активировать TG-бот

Задание №71953 Задание №71952 Задание №20415 Задание №71951 Задание №20414 Задание №20416 Задание №31793 Задание №20408 Задание №38017 Задание №71950 Задание №21583 Задание №75926 Задание №75924 Задание №75922 Задание №75919

Бесплатно

Скачивай наш Тренажер ЕГЭ на iPhone или Android и тренируйся в любое время и в любом месте!