ЕГЭ Задание 27

В этой статье будет разобрано задание 27.

Рассмотрим задачи двадцать седьмого задания из демоверсий последних лет ЕГЭ по информатике.

Данное задание относится к высокому уровню сложности.

Время выполнения задания ≈ 40 минут.

Данное задание проверяет умение выполнять последовательность решения задач анализа данных: сбор первичных данных, очистка и оценка качества данных, выбор и построение модели, преобразование данных, визуализация данных, интерпретация результатов.

Задача 1 (Демоверсия ЕГЭ 2023)

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.
Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

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

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

Типовой пример организации данных во входном файле
6
1 100
2 200
5 4
7 3
8 2
10 190

При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит: 1 ꞏ 2 + 3 ꞏ 1 + 5 ꞏ 1 + 6 ꞏ 1 + 8 ꞏ 2.

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

Решение:

Решение Python

from math import ceil  # Функция для округления в большую сторону
with open('27_A.txt') as file:  # Заменить '27_A.txt' на '27_B.txt'
    N = int(file.readline())  # Общее количество пунктов
    data = [(int(a.split()[0]), int(a.split()[1])) for a in file.readlines()]  # Считываем данные пунктов
    k = data[-1][0] + 1  # Максимальное удаление пункта в порядке их расположения вдоль дороги от нулевой отметки
    a = [0] * k  # Список будем сохранить для каждого пункта(по индексу) количество транспортировочных контейнеров
    summ = 0  # Переменная для суммы транспортных затрат
    for dt in data:  # Перебираем данные для каждого из пунктов
        # Вычисляем количество транспортировочных контейнеров и транспортные затраты
        z = ceil(dt[1] / 36)  # Кол-во пробирок разделить на 36 и округлить
        a[dt[0]] = z  # Сохраняем под номером пункта(для списка a будет индекс) количество контейнеров
        summ += (dt[0] - 1) * z  # Вычисляем затраты и прибавляем к сумме всех затрат
    # Создадим списки s1, s2 для вспомогательных сумм контейнеров доставок для каждого пункта
    # Сумму s1[i] будем отнимать от общей суммы, а s2[i] прибавлять
    s1 = [0]  # Первый 0 для нулевого пункта которого нет в нулевой точке,
    s2 = [0]  # В циклах просто пропустим нулевой пункт
    # Достаточно вычислить для s1[1] и s2[1] (для первого приёмного пункта)
    s1.append(sum(a))  # Сумма всех транспортировочных контейнеров если лаборатория будет в первом пункте
    s2.append(0)  # Значение s2[1] = 0 т.к. левее куда будем идти в цикле нет пунктов
    # Далее можно воспользоваться закономерностью: s1[2] = s1[1]-a[1], s1[3] = s1[2]-a[2]...и т.д.
    # Так же s2[2] = s[1]+a[1], s[3]=s[2]+a[2] и т.д. Заполним списки с помощью цикла
    for i in range(2, k):
        s1.append(s1[i - 1] - a[i - 1])
        s2.append(s2[i - 1] + a[i - 1])
    # Ищем минимальное значение стоимости доставки
    mn = summ  # копируем сумму в переменную для поиска минимума затрат
    for i in range(2, k):   # Перебираем все пункты со второго т.к. сумма для первого была вычислена в переменной summ
        summ = summ - s1[i] + s2[i]  # отнимаем вспомогательную сумму из s1 и прибавляем из s2
        mn = min(mn, summ)  # вычисляем минимум (каждый раз сохраняя новый найденный минимум в переменную mn)
    print(mn)  # Выводим ответ

Ответ: 51063 5634689219329

Задача 2 (Демоверсия ЕГЭ 2024)

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

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

Типовой пример организации данных во входном файле
26
150
–150
20
–200
–300
0

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

Решение:

Решение Python

file1 = open('27_A_2024.txt')
file2 = open('27_B_2024.txt')
# Функция, которая решает задачу для одного файла
def solve(f):
    k = int(f.readline())  # Минимальное количество минут
    n = int(f.readline())  # Количество показаний
    a = []
    a1 = -10000000
    a2 = -10000000
    max_sum = -10000000
    # Заполнить массив показаний
    for i in range(n):
        x = int(f.readline())
        a.append(x)
    # Решение задачи, между показаниями не менее k минут и сумма этих трёх показаний максимальна
    for i in range(2 * k, n):
        a1 = max(a1, a[i - 2 * k])
        a2 = max(a2, a1 + a[i - k])
        max_sum = max(max_sum, a2 + a[i])
    return max_sum  # Вернуть результат
    
# Сохранить результат(ответ) работы функции в переменную
result1 = solve(file1)
result2 = solve(file2)
print(result1, result2)  # Выводим ответы

Ответ: 189536 17210

Задача 3 (Демоверсия ЕГЭ 2025)

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд(точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле: В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px × 10 000, затем целую часть произведения Py × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.

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

Решение:

Решение Python

Для решения данной задачи сначала нужно построить диаграммы по координатам точек в файлах Excel. Затем в коде прописать функцию для вычисления центроида по координатам всех точек кластера. И последним делом стоит уже работать в коде с файлами .txt. Можно конечно решать всё в Excel, но я приведу свой вариант решения на Python, но диаграммы всё же построил в Excel, чтобы прописать потом уже в коде условия проверок вхождения точки в тот или иной кластер. Построить диаграмму в Excel — элементарно:

1. Выделяем данные во всех ячейках.
2. Пункт меню Вставка -> Диаграммы -> Вставить точечную или пузырьковую диаграмму.

p.s. Чтобы быстро выделить все данные – выделяем первую строчку(ячейки) данных и нажимаем Ctrl+Shift+End.

def f27(a):  # Функция для вычисления координат x, y центроида. Принимает список с кортежами координат точек
    minimum = 9999999999999  # Условно большое число для хранения минимума, т.е центроида кластера
    x = 0
    y = 0
    for dot1 in a:  # Перебираем все точки 1 кластера
        d = 0  # Центр кластера
        for dot2 in a:  # Перебираем остальные все точки, чтобы в формуле ниже вычислять пары точек
            d += ((dot2[0] - dot1[0]) ** 2 + (dot2[1] - dot1[1]) ** 2) ** 0.5
        if d < minimum:  # Если получился меньше то заменяем минимум и сохраняем координаты x и y
            x = dot1[0]
            y = dot1[1]
            minimum = d
    return x, y  # Вернуть координаты центроида


with open('demo_2025_27_А.txt') as f1:
    f1.readline()  # Первая строчка с надписью X Y нам не нужна
    a1 = []
    a2 = []
    for s in f1.readlines():  #
        s = s.replace(',', '.').split()  # Чтобы создать из строк дробное число меняем , на .
        # Принадлежит ли точка 1 кластеру (чтобы задать условие, нужно посмотреть на данные в Excel на точечном графике)
        if float(s[0]) < 1:  # Если x < 1
            a1.append((float(s[0]), float(s[1])))  # Добавление в список координат точек кластера 1
        else:
            a2.append((float(s[0]), float(s[1])))  # Добавление в список координат точек кластера 2
    x1, y1 = f27(a1)  # Вызов функции вычисления координат центроида
    x2, y2 = f27(a2)
    Px = int(((x1 + x2) / 2) * 10000)  # Среднее арифметическое по x
    Py = int(((y1 + y2) / 2) * 10000)  # Среднее арифметическое по y
    print(Px, Py)  # Ответ задание файла A

# Для второго файла меняется только вычисление средних арифметических и условия попадания точки в кластер
with open('demo_2025_27_Б.txt') as f2:
    f2.readline()
    a1 = []
    a2 = []
    a3 = []
    for s in f2.readlines():
        s = s.replace(',', '.').split()
        # Чтобы прописать условия для попадания точки в кластер - строим в Excel файле точечную диаграмму
        if float(s[0]) < 3 and float(s[1]) < 4:
            a1.append((float(s[0]), float(s[1])))
        else:
            if float(s[0]) < 5 and float(s[1]) > 6:
                a2.append((float(s[0]), float(s[1])))
            else:
                a3.append((float(s[0]), float(s[1])))
    x1, y1 = f27(a1)
    x2, y2 = f27(a2)
    x3, y3 = f27(a3)
    Px = int(((x1 + x2 + x3) / 3) * 10000)
    Py = int(((y1 + y2 + y3) / 3) * 10000)
    print(Px, Py)

Ответ:
10738 30730
37522 51277

Задача 4 (Демоверсия 2026)

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле:

В файле A хранятся координаты точек двух кластеров, где H = 6 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000.
В файле Б хранятся координаты точек трёх кластеров, где H = 6, W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична структуре в файле А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px – минимальную из абсцисс центров кластеров и Py – минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 – расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 – максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке – сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.
Возможные данные одного из файлов проиллюстрированы графиком.

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

Решение:

Решение Python

Для решения данной задачи сначала нужно построить диаграммы по координатам точек в файлах Excel. Затем в коде прописать функцию для вычисления центроида по координатам всех точек кластера. И последним делом стоит уже работать в коде с файлами .txt. Можно конечно решать всё в Excel, но я приведу свой вариант решения на Python, но диаграммы всё же построил в Excel, чтобы прописать потом уже в коде условия проверок вхождения точки в тот или иной кластер.

Чтобы разбить данные по столбцам:

1. Выделяем столбец который нужно разбить
2. Пункт меню Данные -> Текст по столбцам -> с разделителями -> пробел (в нашем случае так) -> Далее > -> общий -> Готово.

Построить диаграмму в Excel — элементарно:

1. Выделяем данные во всех ячейках.
2. Пункт меню Вставка -> Диаграммы -> Вставить точечную или пузырьковую диаграмму.

p.s. Чтобы быстро выделить все данные – выделяем первую строчку(ячейки) данных и нажимаем Ctrl+Shift+End.

def f27(a):  # Функция для вычисления координат x, y центроида. Принимает список с кортежами координат точек
    minimum = 9999999999999  # Условно большое число для хранения минимума, т.е центроида кластера
    x = 0
    y = 0
    for dot1 in a:  # Перебираем все точки 1 кластера
        d = 0  # Центр кластера
        for dot2 in a:  # Перебираем остальные все точки, чтобы в формуле ниже вычислять пары точек
            d += ((dot2[0] - dot1[0]) ** 2 + (dot2[1] - dot1[1]) ** 2) ** 0.5
        if d < minimum:  # Если получился меньше, то заменяем минимум и сохраняем координаты x и y
            x = dot1[0]
            y = dot1[1]
            minimum = d
    return x, y  # Вернуть координаты центроида


with open('DEMO_27_A.txt') as f1:
    f1.readline()  # Первая строчка с надписью X Y нам не нужна
    a1 = []
    a2 = []
    for s in f1.readlines():  #
        s = s.replace(',', '.').split()  # Чтобы создать из строк дробное число меняем , на .
        # Принадлежит ли точка 1 кластеру (чтобы задать условие, нужно посмотреть на данные в Excel на точечном графике)
        if float(s[1]) < 8:  # Если y < 8
            a1.append((float(s[0]), float(s[1])))  # Добавление в список координат точек кластера 1
        else:
            a2.append((float(s[0]), float(s[1])))  # Добавление в список координат точек кластера 2
    x1, y1 = f27(a1)  # Вызов функции вычисления координат центроида
    x2, y2 = f27(a2)
    Px = int(min(x1, x2) * 10000)  # минимальная из абсцисс центров кластеров
    Py = int(min(y1, y2) * 10000)  # минимальная из ординат центров кластеров
    print(Px, Py)  # Ответ на задание файла A

# Для второго файла меняется только вычисление средних арифметических и условия попадания точки в кластер
with open('DEMO_27_B.txt') as f2:
    f2.readline()
    a1 = []
    a2 = []
    a3 = []
    for s in f2.readlines():
        s = s.replace(',', '.').split()
        # Чтобы прописать условия для попадания точки в кластер - строим в Excel файле точечную диаграмму
        if 10 < float(s[1]) < 20:
            a1.append((float(s[0]), float(s[1])))
        elif 10 < float(s[0]) < 18 and 20 < float(s[1]) < 27:
            a2.append((float(s[0]), float(s[1])))
        elif float(s[0]) > 18 and float(s[1]) < 30:
            a3.append((float(s[0]), float(s[1])))
    all_list = [a1, a2, a3]  # Формируем список для точек всех 3 кластеров
    all_list.sort(key=lambda a: len(a))  # сортируем списки по количеству точек в них
    x1, y1 = f27(all_list[0])  # координаты центроида где меньше всего точек
    x2, y2 = f27(all_list[1])
    x3, y3 = f27(all_list[2])  # координаты центроида где больше всего точек
    Q1 = int(((x1 - x3) ** 2 + (y1 - y3) ** 2) ** 0.5 * 10000)  # расстояние между центрами кластеров с минимальным и максимальным количеством точек
    r1_max = 0  # максимальное расстояние от центроида до одной из точек в кластере 1
    for a in all_list[0]:
        d = ((x1 - a[0]) ** 2 + (y1 - a[1]) ** 2) ** 0.5
        r1_max = max(d, r1_max)
    r2_max = 0 # максимальное расстояние от центроида до одной из точек в кластере 2
    for a in all_list[1]:
        d = ((x2 - a[0]) ** 2 + (y2 - a[1]) ** 2) ** 0.5
        r2_max = max(d, r2_max)
    r3_max = 0 # максимальное расстояние от центроида до одной из точек в кластере 3
    for a in all_list[2]:
        d = ((x3 - a[0]) ** 2 + (y3 - a[1]) ** 2) ** 0.5
        r3_max = max(d, r3_max)
    r_max = max(r1_max, r2_max, r3_max)  # найдем максимум из всех трёх кластеров
    Q2 = int(r_max * 10000)  # максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров
    print(Q1, Q2)  # Ответ на задание файла B

Ответ:
38471 | 61225
142058 | 25299