Имеется набор данных, состоящий из четверок положительных целых чисел. Необходимо выбрать из каждой четверки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 6 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
В ответе введите результаты для файлов A и B без разделителей.
Метод минимальных разностей
f = open(’27B.txt’)
n = int(f.readline())
k = 6 # Число, которому сумма не должна быть кратна
mr = 10 ** 10 # Минимальная разность
s = 0 # Максимальная сумма
for i in range(n):
# Считывание чисел по возрастанию с помощью сортировки sorted()
x, y, z, w = sorted(map(int, f.readline().split()))
s += w # Прибавляем наибольшее число из четвёрки
d1 = w - z # Разность для возможной замены на макс. числа на предмакс. число
d2 = w - y # Разность для возможной замены на макс. числа на предмин. число
d3 = w - x # Разность для возможной замены на макс. числа на мин. число
for d in d1, d2, d3: # Перебираем разности
# Если разность d меньше минимальной разности mr,
# и при этом d не кратно k для изменения остатка
if (d < mr) and (d % k != 0):
mr = d
if s % k == 0: # Если сумма по итогу оказалась кратна k
s -= mr # Отнимаем от максимальной суммы минимальную разность
print(s)
Метод частичных сумм
f = open(’27B.txt’)
n = int(f.readline())
k = 6
smax = [0] * k #здесь будут храниться максимальные суммы для каждого из остатков при делении на 6
#первый элемент — макс.сумма, которая при делении на 6 дает остаток 0
#второй элемент — макс.сумма, которая при делении на 6 дает остаток 1
#третий элемент — макс.сумма, которая при делении на 6 дает остаток 2 и так далее
for i in range(n):
# Сохраним здесь числа из текущей четвёрки
quart = list(map(int, f.readline().split()))
# Формируем суммы с текущими числами
sums = [x + y for x in smax for y in quart]
# Копируем smax во временную переменную smax_temp для сравнения сумм
smax_temp = smax.copy()
# Сравниваем получившиеся суммы с суммами из smax_temp, записываем результат
for x in sums:
smax_temp[x % k] = max(smax_temp[x % k], x)
# Копируем получившийся список в smax
smax = smax_temp.copy()
print(smax)
a = smax.pop(0) #удаляем первый элемент, так как у него остаток 0 при делении на 6
print(max(smax))