Тема 26. Программирование - Обработка целочисленной информации с использованием сортировки

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

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

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

Задача 1#52470

Задание выполняется с использованием прилагаемых файлов

В текстовом файле записан набор натуральных чисел, не превышающих 109.  Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чисел, что их сумма тоже присутствует в файле, и чему равна наибольшая из сумм таких пар.

Входные данные.

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N  строк содержит одно число. В ответе запишите два целых числа: сначала количество пар, затем наибольшую сумму.

Под парой подразумевается любые два различные элемента последовательности.

Пример входных данных:

5

1

4

9

16

25

В данном случае есть одна подходящая пара: 9  и 16  (сумма 25  ).

В ответе надо записать числа 1  и 25  .

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

Решение через бин. поиск

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 = []
counter = 0
max_summ = 0
for i in range(n):
    a.append(int(f.readline()))

a = sorted(a)
for i in range(len(a)):
    for j in range(i+1, len(a)):
        if bin_search(a, a[i] + a[j]):
            counter += 1
            max_summ = max(max_summ, a[i] + a[j])
print(counter, max_summ)

Решение через поиск по множеству

f = open(’1.txt’)
n = int(f.readline())
a = []
counter = 0
max_summ = 0
for i in range(n):
    a.append(int(f.readline()))

for i in range(len(a)):
    for j in range(i+1, len(a)):
        if (a[i] + a[j]) in a:
            counter += 1
            max_summ = max(max_summ, a[i] + a[j])
print(counter, max_summ)

Ответ: 386 250000

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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