Задание выполняется с использованием прилагаемых файлов
В текстовом файле записан набор натуральных чисел, не превышающих 
Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чисел, что числа в паре имеют разную чётность, а их сумма тоже присутствует в файле, и чему равна наименьшая из сумм таких пар.
Входные данные.
Первая строка входного файла содержит целое число 
— общее количество чисел в наборе. Каждая из следующих 
строк содержит одно число. В ответе запишите два целых числа: сначала количество пар, затем наименьшую сумму.
Под парой подразумевается любые два различные элемента последовательности.
Пример входных данных:
В данном случае есть две подходящие пары: 
и 
(сумма 
), 
и 
(сумма 
).
В ответе надо записать числа 
и 
.
Неэффективное решение (в рамках этого задания), через бин. поиск
def bin_search(a, x):
n = len(a)
left = -1
right = n
while right - left > 1:
middle = (left + right) // 2
if a[middle] >= x:
right = middle
else:
left = middle
if right != n and a[right] == x:
return True
else:
return False
f = open(’1.txt’)
n = int(f.readline())
a, odd, even = [], [], []
counter = 0
min_summ = 10 ** 10
for i in range(n):
x = int(f.readline())
if x % 2 == 0:
even.append(x)
else:
odd.append(x)
a.append(x)
a = sorted(list(set(a))) # Уменьшаем количество элементов до уникальных
for i in odd:
for j in even:
if bin_search(a, i + j):
counter += 1
min_summ = min(min_summ, i + j)
print(counter, min_summ)
Эффективное решение через проход по множеству (поиск в среднем происходит за 1 операцию).
f = open(’task 5.txt’)
n = int(f.readline())
a, odd, even = [], [], []
counter = 0
min_summ = 10 ** 10
for i in range(n):
x = int(f.readline())
if x % 2 == 0:
even.append(x)
else:
odd.append(x)
a.append(x)
a = set(a) # Перебор (in) идет за O(n)
for i in odd:
for j in even:
if (i + j) in a:
counter += 1
min_summ = min(min_summ, i + j)
print(counter, min_summ)