27 задание ЕГЭ информатика

Анализ данных: кластеризация

2 балла ≈ 40 мин уровень В

Задание 27 – файлы A и Б с координатами точек (звёзд), которые образуют несколько кластеров. Нужно разделить точки на кластеры, найти центр каждого (точку кластера с минимальной суммой расстояний до остальных) и вычислить требуемые величины. Ответ – четыре числа (по два для A и Б), обычно целая часть величины × 10 000. 2 балла.

Алгоритм

Посмотри на данные: построй точечную диаграмму в Excel – кластеры видны глазами, легко подобрать границы.
Раздели точки на кластеры: по границам (if x < 5 …) или автоматически – поиском связных групп (точки ближе R друг к другу – в одном кластере).
Отбрось аномалии – одиночные точки, не входящие в кластеры.
Центр кластера: перебери все его точки, для каждой посчитай сумму расстояний до остальных, возьми минимум.
Посчитай величины из условия и умножь на 10 000, возьми целую часть int(…).

Шаблон на Python

from math import dist

pts = [tuple(map(float, line.replace(",", ".").split())) for line in open("27A.txt")]
R = 1.0                                   # порог соседства, подбери по диаграмме
clusters, used = [], set()
for i in range(len(pts)):
    if i in used:
        continue
    used.add(i)
    stack, cl = [i], []
    while stack:                          # обход связной группы
        j = stack.pop()
        cl.append(pts[j])
        for k in range(len(pts)):
            if k not in used and dist(pts[j], pts[k]) < R:
                used.add(k)
                stack.append(k)
    clusters.append(cl)

def center(cl):
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

cs = [center(cl) for cl in clusters if len(cl) > 3]   # аномалии отброшены
px = min(c[0] for c in cs)
py = min(c[1] for c in cs)
print(int(abs(px) * 10000), int(abs(py) * 10000))

Для файла Б (до 10 000 точек) обход «каждый с каждым» медленный: раздели точки по координатным границам, подобранным по диаграмме, – это быстро и надёжно.

Разобранный пример. Кластер из точек (0; 0), (1; 0), (2; 0). Суммы расстояний: для (0; 0) – 1 + 2 = 3, для (1; 0) – 1 + 1 = 2, для (2; 0) – 3. Центр – (1; 0). Если ответ – абсцисса центра × 10 000, записываем 10000.

Ловушки: центр – это точка кластера (медоид), а не среднее арифметическое координат; запятая вместо точки в дробях файла; аномальные точки в файле Б нельзя включать в кластеры; «целая часть абсолютной величины» – int(abs(…)), без округления.

На экзамене

Начни с диаграммы в Excel: увидишь число кластеров, границы и аномалии.
math.dist(p, q) считает евклидово расстояние между точками-кортежами.
Даже если файл Б не получается – реши файл A: это уже 1 балл.

Разобранные задания 27 из открытого банка ФИПИ

Пример 1 · код ФИПИ AAB9D2

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:

$d (A, B) = \sqrt{{(x_{2} - x_{1})}^{2} + {(y_{2} - y_{1})}^{2}} .$

В файле A хранятся координаты точек двух кластеров, где H = 6, W = 6 для каждого кластера. В каждой строке записана информация о расположении на карте одной точки: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 8, W = 8 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична структуре в файле А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: P_x – среднее арифметическое абсцисс центров кластеров, и P_y – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке – сначала абсолютное значение целой части произведения P_x × 10 000, затем абсолютное значение целой части произведения P_y × 10 000 для файла А; во второй строке – аналогичные данные для файла Б.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.

Рисунок к заданию

Файл к заданию (ZIP)

Показать ответ и решение

Ответ: 26216 24182 150891 63754

Кластеры выделяем как компоненты связности точек (соседи на расстоянии ≤ r): в A – 2 кластера по 50 точек, в Б – 3 кластера.

Центр – точка с минимальной суммой расстояний до остальных точек кластера. A: Px·10⁴ → 26216, Py·10⁴ → 24182; Б: 150891 и 63754.

Пример 2 · код ФИПИ BED6E1

Рисунок к заданию

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

На каждом 3-м километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна 3N километров. Нулевой километр и 3N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов расположен в одном из пунктов сбора мусора таким образом, что общая стоимость доставки мусора из всех пунктов минимальна.

Определите минимальную суммарную стоимость доставки мусора из всех пунктов сбора в центр переработки отходов.

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

Дано два входных файла (файл A и файл B), каждый из которых
в первой строке содержит число N (1 ≤ N ≤ 10 000 000) $-$ количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих N строк находится число $-$ количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем $-$ для файла B.

Типовой пример организации данных во входном файле

При таких исходных данных, если контейнеры установлены на каждом километре автодороги, необходимо открыть центр переработки в пункте 6. В этом случае сумма транспортных затрат составит:

1 $\cdot$ 7 + 0 $\cdot$ 19 + 1 $\cdot$ 8 + 2 $\cdot$ 20 + 3 $\cdot$ 5 + 2 $\cdot$ 13.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Файл к заданию (ZIP)

Показать ответ и решение

Ответ: 471228 49113954961677

Пункты стоят через 3 км на кольце из N пунктов: расстояние $3 \cdot \min (d, N - d)$ . Стоимость для каждого центра считаем за O(1) через префиксные суммы $\sum a_{i}$ и $\sum i a_{i}$ по утроенному массиву.

Минимум: A – 471228, B – 49113954961677.

Пример 3 · код ФИПИ EF3033

Рисунок к заданию

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

По каналу связи передаётся последовательность натуральных чисел – показания прибора. В течение N мин. (N – натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической сети и передаёт его на сервер.

Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее K мин.,
а произведение этих трёх чисел было максимально возможным. Запишите в ответе найденное произведение.

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

Даны два входных файла (файл A и файл B), каждый из которых
в первой строке содержит натуральное число K – минимальное количество минут, которое должно пройти между моментами передачи показаний, а во второй – количество переданных показаний N (1 ≤ N ≤ 10 000 000, N > K). В каждой из следующих
N строк находится одно натуральное число, не превышающее 10 000 000, которое обозначает значение напряжения в соответствующую минуту.

Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле

При таких исходных данных искомая величина равна 135 – это произведение значений, зафиксированных на первой, третьей
и шестой минутах измерений.

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

Файл к заданию (ZIP)

Показать ответ и решение

Ответ: 172675914708 130708226880

Для средней позиции j берём максимум слева до $j - K$ и максимум справа от $j + K$ (префиксные/суффиксные максимумы) – O(N).

A: 172675914708, B: 130708226880.

Частые вопросы о задании 27

Сколько баллов даёт задание 27 ЕГЭ по информатике?

Максимум – 2 первичных балла. Норма времени на экзамене – около 40 мин. Уровень сложности – В.

Что проверяет задание 27?

Как подготовиться к заданию 27?

Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.