Стрим #45. ЕГЭ по информатике 2019, 11 класс. Задача 27

Решаем задачи №27

За мат, КАПС, обсуждение компьютерного ЕГЭ, политоту, спам, любое упоминание доты и "ауе" в чате - перманентный бан.

-------

Для предметных комиссий субъектов РФ:

[denmazlov]

Так решение этой задачи могло бы выглядеть на Python3:



def prg46():
dots=[[float(input()), float(input())] for dot in range(int(input()))]
base_x=[dot[0] for dot in dots if dot[1]==0]

print(0 if not base_x or len(dots)<3 else 0.5 * max(abs(dot[1]) for dot in dots) * (max(base_x) - min(base_x)) )


Три строчки.

1) формируется массив вводимых точек. Контроля корректности ввода данных, как и в примере на Паскале, естественно, нет.
2) формирует массив X-координат точек, лежащих на оси X (если такие существуют)
3) распечатка результата с проверками: а) not base_x - нет ни одной точки лежащей на оси X. А так base_x будет содержать массив координат X для точек, лежащих на OX
б) len(dots)<3 - ввели меньше 3 точек (т.е. не хватает вершин для треугольника), впрочем это избыточная проверка - можно убрать, т.к. если на OX будет всего одна вершина, то при вычислении длины основания совпадут и максимальная и минимальная координата X и длина получится равной нулю.


Так можно было бы сделать эту задачу через формулу Герона:


def prg46b():
from math import sqrt as sqrt
dots, square=[[float(input()), float(input())] for dot in range(int(input()))], 0
for a in dots:
for b in dots:
for c in dots:
if a!=b!=c and (a[1]==b[1]==0 or a[1]==c[1]==0 or c[1]==b[1]==0):
ab=sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
ac=sqrt((a[0]-c[0])**2 + (a[1]-c[1])**2)
cb=sqrt((c[0]-b[0])**2 + (c[1]-b[1])**2)
pp=(ab+ac+cb)/2


if max_square<triangle_square:
max_square=triangle_square
print(0 if not max_square else max_square)



Существенно длиннее текст получается, хотя скорость выполнения примерно такая же.

[alexeykozlovsky]

По-моему в задачах, где спрашивается найти количество пар, элементы которых находятся на расстоянии не менее... и произведение делится на ПРОСТОЕ число, можно применять более простой и быстрый алгоритм. Ну, не знаю, насколько он быстрее, но, как по мне, удобнее. Но это только при условии, что число простое.
Либо вот так:
count = 0
couples = 0
const = 4
n = int(input())
for i in range(n):
current = int(input())
if current % 29 == 0:
if i >= const and n - i >= const:
couples += n - count - 2*const
elif i >= const or n - i >= const:
couples += n - count - const
count += 1
print(couples)

Либо вот так:
count = 0
couples = 0
const = 4
n = int(input())
if n <= const:
#Не знаю, надо ли здесь запрашивать ввод,
#в любом случае кол-во пар будет равно 0
print(couples)
exit()
for i in range(n):
current = int(input())
if current % 29 == 0:
if i >= const and n - i >= const:
couples += n - count - 2*const
else:
couples += n - count - const
count += 1
print(couples)

Мне лично больше нравится второй вариант, так как в задаче требуется только посчитать кол-во пар. Во втором решении сразу откидываются варианты, где точно кол-во пар будет 0. Но на ЕГЭ скорее всего за exit() или за то, что не запросил ввод чисел, снимут баллы. Ну, суть алгоритма одна и та же. Мне кажется, что для задач, где проверяется делимость на простые числа, этот алгоритм отлично подходит

[envy]

Вопрос о 46й задаче
Можно ли решать без счётчика k? ведь если есть только одна точка на ОХ, то разность xmin и xmax даст 0, а если таких точек нет, то для этого достаточно сделать условие |xmax|<>|xmin|

[dreamchalk]

А как узнавать, когда стрим, чтобы успеть попасть? А то хочется иногда вопросы онлайн задавать, когда что-то не совсем понятно

[МаксимЗотов-щц]

У меня есть сомнения насчёт R := R + i на 1:57:15. Цикл выполняется до n - 4 по причине того, что ранее его 4 элементам уже были присвоены значения, а R := R + i - 4 нужен для того, чтобы исключить те элементы, которые находятся на меньшем чем 4 расстоянии от введённого элемента, кратного 29.
К примеру, здесь именно так и сделано, т.е. R := R + i - 4:

[vppnzoi]

Кто смотрел, скажите, пожалуйста, Бу начал объяснять с нуля или сразу взял задачи посложнее?

[eugenerudukh]

Нужно строки учить, если это разбиралось на стриме, сори