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 = [] counter = 0 min_summ = 10**12 for i in range(n): a.append(int(f.readline())) a = sorted(list(set(a))) # Уменьшаем количество элементов до уникальных for i in range(len(a)): for j in range(i+1, len(a)): if (a[i]**2 + a[j]**2)**0.5 == int((a[i]**2 + a[j]**2)**0.5): if bin_search(a, a[i]**2 + a[j]**2): counter += 1 min_summ = min(min_summ, a[i]**2 + a[j]**2) print(counter, min_summ)
Решение через поиск по множеству
f = open(’1.txt’) n = int(f.readline()) a = [] counter = 0 min_summ = 10**12 for i in range(n): a.append(int(f.readline())) b = set(a) # Уменьшаем количество элементов до уникальных for i in range(len(a)): for j in range(i+1, len(a)): if (a[i]**2 + a[j]**2)**0.5 == int((a[i]**2 + a[j]**2)**0.5): if (a[i]**2 + a[j]**2) in b: counter += 1 min_summ = min(min_summ, (a[i]**2 + a[j]**2)) print(counter, min_summ)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
