Тема . (старое) 27. Программирование

.05 Макс/мин, кол-во пар, сумма/разность кратна/не кратна

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела (старое) 27. программирование
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#63440

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

Входные данные: Даны два входных файла(файл А и файл В), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000)  . Каждая из следующих N строк содержит одно натуральное число, не превышающее 108  .

Пример входного файла:

6

905

573

971

947

742

644

Наибольшая из сумм - 3396.

В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла В.

Вложения к задаче
Показать ответ и решение

Для А

from itertools import combinations # с помощью combinations из модуля itertools можно удобно брать пары чисел при этом не печатая два цикла
f = open(’27-11a.txt’)
mx = 0
n = int(f.readline())
a = [int(x) for x in f]#список всех чисел в файле
for w,x,y,z in combinations(a,4):#эта строчка заменяет 4 строчки циклов
    if (w+x+y+z) % 6 == 0:#если сумма чисел кратна 6,то она нам подходит
        mx = max(mx,w+x+y+z)#сравниваем с максимумом
print(mx)

Для Б

# Это решение основанно на одном простом свойстве делимости:
# сумма чисел кратна числу если сумма их остатков от деления на число кратно числу

# Считываем файл, сортируем по убыванию список всех чисел в файле,
# поскольку нас интересует максимальная сумма
a = sorted([int(x) for x in open(’27-11b.txt’)][1:])[::-1]
d = []  # список, в котором будут храниться подходящие нам числа
for j in range(6):  # перебор всевозможных остатков при делении на 6
    for x in a:
        # если остаток x от деления на 6 равен j,
        # то мы добавляем это число в список
        if x % 6 == j:
            d += [x]
        if len([x for x in d if x % 6 == j]) == 4:
            break
        # условием прерывания сбора подходящих нам чисел служит то,
        # что в списке есть 4 числа с одним и тем же остатком при делении на 6,
        # именно 4 потому что в задаче мы должны взять ровно 4 числа

mx = 0
for x in range(len(d) - 3):
    for y in range(x + 1, len(d) - 2):
        for z in range(y + 1, len(d) - 1):
            for w in range(z + 1, len(d)):
                # 4 цикла, с помощью которых мы будем рассматривать
                # все возможные четверки в нашем списке d
                if (d[x] + d[y] + d[z] + d[w]) % 6 == 0:
                    mx = max(mx, (d[x] + d[y] + d[z] + d[w]))
print(mx)

Ответ: 3852 399981558

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!