Ошибка.
Попробуйте повторить позже
Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех таких чисел была максимальна и кратна 5 или 11, но не 5 и 11 одновременно. Определите, какую максимальную сумму, удовлетворяющую условиям задачи можно получить.
Формат входных данных
Набор данных состоит из пар натуральных чисел.
Первая строка входных данных содержит число n — количество строк, . Следующие n строк содержат пару натуральных чисел не превышающие 10000.
Формат выходных данных
Программа должна вывести целое число — максимальную сумму.
Пример:
Ответом для примера будет:
Максимальная сумма, которую можно получить равна (5+50), но она кратна одновременно и 5, и 11, что недопустимо по условию задачи. Сумма 3+8 подходит по условиям задачи и является максимальной.
По китайской теореме об остатках гарантируется, что при перемножении взаимнопростых чисел найдется сумма, которая будет иметь какой-то остаток при делении на произведение и при этом будет кратно лишь одному из чисел, указанных в произведении.
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%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!