.04 Пары/тройки чисел, выбрать из каждой, кратность
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех
таких чисел была максимальна и кратна 
или 
, но не 
и 
одновременно.Программа должна напечатать одно
число — максимальную сумму удовлетворяющую условиям задачи.
Входные данные:
Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке одно целое число
— количество чисел. Каждая из следующих 
строк содержит два натуральных числа не
превышающих 
.
Пример входных данных:
Максимальная сумма, которую можно получить равна 
, но она кратна одновременно и 
, и 
, что
недопустимо по условию задачи. Сумма 
подходит по условиям задачи и является максимальной. Ответом для
примера будет: 
Метод минимальных разностей
f = open("Задание_27_A__ozaw.txt")
n = int(f.readline())
mr = [10 ** 10] * (7 * 11) # Список для хранения минимальных разностей по остаткам
maxS = 0 # Максимальная сумма чисел
for i in range(n):
a, b = map(int, f.readline().split()) # Считываем числа
maxS += max(a, b) # Прибавляем к сумме максимальное число из пары
r = abs(a - b) # Разность между элементами
mr1 = mr[:] # Создаём копию списка разностей
for j in range(77):
# Ищем минимальную сумму нескольких разностей
if r + mr1[j] < mr[(r + mr1[j]) % 77]:
mr[(r + mr1[j]) % 77] = r + mr1[j]
# Если текущая разность меньше разности в списке
if r < mr[r % 77]:
mr[r % 77] = r
# Сумма делится на оба числа
if maxS % 7 == 0 and maxS % 11 == 0:
# Нужно найти такую мин. разность, которая изменит только один остаток:
# либо остаток от деления на 7, либо остаток от деления на 11
d = 10 ** 10
for j in range(77):
count = 0 # Количество чисел, на которое делится сумма
if (maxS - mr[j]) % 7 != 0:
count += 1
if (maxS - mr[j]) % 11 != 0:
count += 1
if count == 1: # Если сумма не делится на одно число, запоминаем разность
d = min(mr[j], d)
maxS -= d # Вычитаем итоговую мин. разность
# Сумма не делится ни на одно число
elif maxS % 7 != 0 and maxS % 11 != 0:
# Также нужно найти мин. разность, которая даст кратность только одному числу
d = 10 ** 10
for j in range(77):
count = 0 # Количество чисел, на которое делится сумма
if (maxS - mr[j]) % 7 == 0:
count += 1
if (maxS - mr[j]) % 11 == 0:
count += 1
if count == 1: # Если сумма делится на одно число, запоминаем разность
d = min(mr[j], d)
maxS -= d # Вычитаем итоговую мин. разность
print(maxS) # Выводим итоговую сумму выбранных чисел
Метод частичных сумм
file = open("Задание_27_A__ozaw.txt")
n = int(file.readline())
a = [-1000000000000] * 77
a[0] = 0
for i in range(n):
x, y = [int(j) for j in file.readline().split()]
a_new = [-1000000000000] * 77
for j in range(77):
t = (a[j] + x) % 77
a_new[t] = max(a_new[t], a[j] + x)
for j in range(77):
t = (a[j] + y) % 77
a_new[t] = max(a_new[t], a[j] + y)
a = a_new.copy()
ans = -1000000000000
for i in range(77):
if (i % 7 == 0 and i % 11 != 0) or (i % 7 != 0 and i % 11 == 0):
ans = max(ans, a[i])
print(ans)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
