27.05 Макс/мин, кол-во пар, сумма/разность кратна/не кратна
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары различных
элементов последовательности, у которых различные остатки от деления на 
и хотя бы одно из чисел делится на
. Среди таких пар, необходимо найти пару с максимальной суммой элементов. В качестве ответа выведите данную
максимальную сумму.
Входные данные:
В первой строке входных данных задаётся количество чисел 
(1 
N 
1000). В каждой из последующих 
строк записано одно натуральное число, не превышающее 
. В качестве результата программа должна напечатать
максимальную сумму элементов среди найденных пар.
Пример организации исходных данных во входном файле:
Пример выходных данных для приведённого выше примера входных данных:
В ответе укажите два числа: сначала сумму искомой пары для файла А, затем для файла B.
Решение 1 (неэффективное)
f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
for j in range(i + 1, n):
if a[i] % 100 != a[j] % 100:
if (a[i] % 6 == 0) or (a[j] % 6 == 0):
ans = max(ans, a[i] + a[j])
print(ans)
Решение 2 (эффективное)
f = open("9.txt")
n = int(f.readline())
# Список максимальных чисел с определенными остатками от деления, которые кратны 6
maxim_d_6 = [0]*100
# Список максимальных чисел с определенными остатками от деления, которые НЕ кратны 6
maxim_d = [0]*100
maxim = 0
for i in range(n):
x = int(f.readline())
# Если x кратен 6, к нему в пару можно ставить и кратные и некратные 6 числа
if x % 6 == 0:
for j in range(100):
# Если остатки от деления разные - обновляем максимум
if j != x % 100:
maxim = max(x+maxim_d_6[j], x+maxim_d[j], maxim)
# Обновляем максимальное число с определенным остатком
maxim_d_6[x % 100] = max(maxim_d_6[x % 100], x)
# Если x НЕ кратен 6, к нему в пару можно ставить только кратные 6 числа
else:
for j in range(100):
# Если остатки от деления разные - обновляем максимум
if j != x % 100:
maxim = max(x+maxim_d_6[j], maxim)
# Обновляем максимальное число с определенным остатком
maxim_d[x % 100] = max(maxim_d[x % 100], x)
print(maxim)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
