ЕГЭ 27

Задание 27 ЕГЭ по информатике: 27. Алгоритмы обработки данных — вариант 2027-Носиров-2

Вариант 2027-Носиров-2

Варианты

Задание 27 ЕГЭ по информатике: 27. Алгоритмы обработки данных — вариант 2027-Носиров-2

2027-Носиров-2

Секундомер

0 XP

0 / 0

Скачать 27.txt

(Э. Носиров) Задание выполняется с использованием файла 27.txt.

Для каждой частицы на плоскости заданы декартовы координаты x, y, проекции скорости V_x, V_y, масса m и признак, обозначенный римским числом от I до VII. Числовые величины для всех частиц даны в одинаковых единицах измерения.

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

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

Такое разбиение существует и единственно.

Центром кластера называется его частица, для которой сумма модулей разностей её энергии с энергиями всех остальных частиц этого кластера минимальна.

Центр каждого кластера единственный.

Найдите два числа: Q1 — наибольшее евклидово расстояние между двумя частицами одного кластера, обе из которых имеют признак V; Q2 — сумму кинетических энергий центров всех пяти кластеров.

В ответе запишите сначала целую часть произведения Q1 · 10 000, затем целую часть произведения Q2 · 10 000.

Для выполнения задания напишите программу.

Файл содержит не более 10 000 строк без заголовка.

Каждая строка содержит x, y, V_x, V_y, m и признак в указанном порядке.

Значения разделены пробелами, десятичная часть отделяется запятой.

Абсолютная величина каждого числового значения не превышает 100; массы положительны.

Для справки

Кинетическая энергия частицы вычисляется по формуле

E = m · (V_x² + V_y²) / 2.

Евклидово расстояние между точками вычисляется по формуле

d = √((x₂ - x₁)² + (y₂ - y₁)²).

Пример строк файла:

2,5 -1,0 3,0 4,0 0,4 V
-4,0 6,5 1,0 -2,0 2,0 III
0,0 0,0 2,0 1,0 3,0 VII

Кинетическая энергия частицы в первой строке равна 5.

Пример иллюстрирует формат данных; для решения используйте прилагаемый файл.

(Э. Носиров) Задание выполняется с использованием файла 27.txt.

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

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

Такое разбиение существует и единственно.

Центр каждого кластера единственный.

В ответе запишите сначала целую часть произведения Q1 · 10 000, затем целую часть произведения Q2 · 10 000.

Для выполнения задания напишите программу.

Файл содержит не более 10 000 строк без заголовка.

Каждая строка содержит x, y, V_x, V_y, m и признак в указанном порядке.

Значения разделены пробелами, десятичная часть отделяется запятой.

Абсолютная величина каждого числового значения не превышает 100; массы положительны.

Для справки

Кинетическая энергия частицы вычисляется по формуле

E = m · (V_x² + V_y²) / 2.

Евклидово расстояние между точками вычисляется по формуле

d = √((x₂ - x₁)² + (y₂ - y₁)²).

Пример строк файла:

2,5 -1,0 3,0 4,0 0,4 V
-4,0 6,5 1,0 -2,0 2,0 III
0,0 0,0 2,0 1,0 3,0 VII

Кинетическая энергия частицы в первой строке равна 5.

Пример иллюстрирует формат данных; для решения используйте прилагаемый файл.

Решение 1. Кластеризация по кинетической энергии

Шаг 1. Что дано в файле

from math import hypot

points = []

В каждой строке: координаты x, y, проекции скорости V_x, V_y, масса m и римский признак (I–VII). Числа могут быть с запятой или табуляцией.

Шаг 2. Кинетическая энергия

for line in open("27.txt"):
    line = line.strip().replace("\t", " ")
    if not line:
        continue
    x, y, vx, vy, m, t = line.replace(",", ".").split()
    x, y, vx, vy, m = map(float, [x, y, vx, vy, m])
    e = 0.5 * m * (vx * vx + vy * vy)
    points.append([x, y, e, t])

По формуле из условия: E = ½ m (V_x² + V_y²).

Шаг 3. Пять кластеров по E

points.sort(key=lambda q: q[2])
R = 1.6
cl = [[points[0]]]
for pt in points[1:]:
    if pt[2] - cl[-1][0][2] > R:
        cl.append([])
    cl[-1].append(pt)

При R = 1,6 сортируем частицы по энергии. Новый кластер начинается, когда энергия точки больше энергии первой частицы текущего кластера более чем на R. Получается ровно 5 кластеров.

Шаг 4. Евклидово расстояние

def dist(p1, p2):
    return hypot(p1[0] - p2[0], p1[1] - p2[1])

Расстояние между частицами на плоскости — корень из суммы квадратов разностей координат.

Шаг 5. Центр кластера

def find_center(cluster):
    best = None
    for p in cluster:
        s = sum(abs(p[2] - q[2]) for q in cluster)
        key = (s, p[2])
        if best is None or key < best[0]:
            best = (key, p)
    return best[1]


centers = [find_center(c) for c in cl]

Центр — частица с минимальной суммой модулей разностей кинетической энергии до остальных частиц этого кластера.

Шаг 6. Q1 — частицы с признаком V

q1 = 0.0
for cluster in cl:
    marked = [p for p in cluster if p[3] == "V"]
    for i in range(len(marked)):
        for j in range(i + 1, len(marked)):
            d = dist(marked[i], marked[j])
            if d > q1:
                q1 = d

В каждом кластере берём только частицы с признаком V, перебираем все пары и ищем наибольшее расстояние.

Шаг 7. Q2 — сумма энергий центров

q2 = sum(c[2] for c in centers)

Q2 — сумма кинетических энергий центров всех пяти кластеров.

Шаг 8. Печать ответа

print(int(q1 * 10000), int(q2 * 10000))

В ответе — целые части произведений Q1 × 10 000 и Q2 × 10 000.

Переменная	Значение
нет переменных