Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 16. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В ответе укажите четыре числа: два числа для файла А, числа в паре писать в порядке возрастания, затем, через пробел, числа для файла Б.
Переборное решение:
f = open(’21_A.txt’)
n = int(f.readline())
nums = [int(i) for i in f]
pair = [-10 ** 10] * 2
for i in range(n):
for j in range(i + 1, n):
if abs(nums[i] - nums[j]) % 2 == 0:
if nums[i] % 16 == 0 or nums[j] % 16 == 0:
if nums[i] + nums[j] > sum(pair):
pair = [nums[i], nums[j]]
print(*sorted(pair))
Эффективное решение:
f = open(’21.txt’)
n = int(f.readline())
# Список, где первый индекс - кратность числа 16-и (0 - не кратно, 1 - кратно),
# а второй индекс - остаток от деления на 2
nums = [[-10 ** 10] * 2 for _ in range(2)]
ans = [-10 ** 10] * 2
for i in range(n):
x = int(f.readline())
# Чтобы разность получилась четной, элементы должны
# иметь одинаковые остатки от деления на 2
ost = x % 2
# Если x кратен 16, к нему в пару можно ставить числа и кратные и не кратные 16
if x % 16 == 0:
# Обновляем ответ, записывая в него пару с большей суммой элементов
# Параметр key=sum позволяет функции max вычислять наибольший список исходя
# из суммы его элементов
ans = max(ans, [x, nums[0][ost]], [x, nums[1][ost]], key=sum)
nums[1][ost] = max(x, nums[1][ost])
# Если x не кратен 16, к нему в пару можно ставить только числа кратные 16
else:
ans = max(ans, [x, nums[1][ost]], key=sum)
nums[0][ost] = max(x, nums[0][ost])
print(*sorted(ans))