26.04 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
В текстовом файле записан набор натуральных чисел, не превышающих Необходимо определить, сколько в наборе таких пар нечётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наименьшее из средних арифметических таких пар.
Входные данные:
Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.
Пример входных данных:
6
16
3
21
12
9
6
В данном случае есть две подходящие пары: 3 и 21 (среднее арифметическое 12), 3 и 9 (среднее арифметическое 6). В ответе надо записать числа 2 и 6.
В ответе через пробел запишите два целых числа: сначала количество пар, затем наименьшее среднее арифметическое.
Менее эффективное решение через бин. поиск
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 = [] b = set() for i in range(n): x = int(f.readline()) if x % 2 != 0: a.append(x) b.add(x) b = sorted(list(b)) k = 0 q = 0 minim = 1000000000000000 for i in range(len(a)): q += 1 for j in range(i + 1, len(a)): t = (a[i] + a[j]) // 2 if bin_search(b, t): k += 1 if t < minim: minim = t if q % 100 == 0: print(q) print(k, minim)
Эффективное решение через проход по множеству (поиск в среднем происходит за 1 операцию).
f = open(’Задание_26.txt’) n = int(f.readline()) a = [] b = set() for i in range(n): x = int(f.readline()) if x % 2 != 0: a.append(x) b.add(x) k = 0 minim = 1000000000000000 for i in range(len(a)): for j in range(i + 1, len(a)): t = (a[i] + a[j]) // 2 if t in b: k += 1 if t < minim: minim = t print(k, minim)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!