26.04 Прочие прототипы

Неэффективное решение (в рамках этого задания), через бин. поиск

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)