.04 Пары/тройки чисел, выбрать из каждой, кратность
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех таких чисел была максимальна и кратна 5 или 11, но не 5 и 11 одновременно. Определите, какую максимальную сумму, удовлетворяющую условиям задачи можно получить.
Формат входных данных
Набор данных состоит из пар натуральных чисел.
Первая строка входных данных содержит число n — количество строк, 
. Следующие n строк содержат пару
натуральных чисел не превышающие 10000.
Формат выходных данных
Программа должна вывести целое число — максимальную сумму.
Пример:
Ответом для примера будет: 
Максимальная сумма, которую можно получить равна (5+50), но она кратна одновременно и 5, и 11, что недопустимо по условию задачи. Сумма 3+8 подходит по условиям задачи и является максимальной.
По китайской теореме об остатках гарантируется, что при перемножении взаимнопростых чисел найдется сумма, которая будет иметь какой-то остаток при делении на произведение и при этом будет кратно лишь одному из чисел, указанных в произведении.
Метод минимальных разностей
f = open(’27.txt’)
n = int(f.readline())
mr = [10 ** 10] * (5 * 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(55):
# Ищем минимальную сумму нескольких разностей
if r + mr1[j] < mr[(r + mr1[j]) % 55]:
mr[(r + mr1[j]) % 55] = r + mr1[j]
# Если текущая разность меньше разности в списке
if r < mr[r % 55]:
mr[r % 55] = r
# Сумма делится на оба числа
if maxS % 5 == 0 and maxS % 11 == 0:
# Нужно найти такую мин. разность, которая изменит только один остаток:
# либо остаток от деления на 5, либо остаток от деления на 11
d = 10 ** 10
for j in range(55):
count = 0 # Количество чисел, на которое делится сумма
if (maxS - mr[j]) % 5 != 0:
count += 1
if (maxS - mr[j]) % 11 != 0:
count += 1
if count == 1: # Если сумма не делится на одно число, запоминаем разность
d = min(mr[j], d)
maxS -= d # Вычитаем итоговую мин. разность
# Сумма не делится ни на одно число
elif maxS % 5 != 0 and maxS % 11 != 0:
# Также нужно найти мин. разность, которая даст кратность только одному числу
d = 10 ** 10
for j in range(55):
count = 0 # Количество чисел, на которое делится сумма
if (maxS - mr[j]) % 5 == 0:
count += 1
if (maxS - mr[j]) % 11 == 0:
count += 1
if count == 1: # Если сумма делится на одно число, запоминаем разность
d = min(mr[j], d)
maxS -= d # Вычитаем итоговую мин. разность
print(maxS) # Выводим итоговую сумму выбранных чисел
Метод частичных сумм
n = int(input()) ans = [0]*(5*11) for i in range(n): a = [int(i) for i in input().split()] ans_new = [-1000000000]*55 for k in range(len(a)): for j in range(55): ost = (ans[j] + a[k]) % 55 if ans[j] + a[k] > ans_new[ost]: ans_new[ost] = ans[j] + a[k] ans = ans_new print(max(max([i*(i % 5 == 0 and i % 11 != 0) for i in ans]), \ max([i*(i % 5 != 0 and i % 11 == 0) for i in ans]) ))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
