ЕГЭ 27

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

Вариант 2027-фипи-октябрь

Варианты

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

2027-фипи-октябрь

Секундомер

0 XP

0 / 0

Скачать 27.txt

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

Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами от I до VII (в римской системе счисления).

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

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

Если таких частиц несколько, центром кластера считается та из них, у которой кинетическая энергия наибольшая.

В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости V_x и V_y, масса m и признак.

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

Значения даны в одинаковых для всех частиц единицах измерения, обозначения единиц измерения в файле не приводятся.

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции.

Количество строк в файле не превышает 10 000.

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

Известно, что все описанные в файле частицы подразделяются ровно на 4 кластера (K=4) с R=2,0 для каждого.

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

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

Иллюстрация к заданию

Для справки

Кинетическая энергия E частицы массы m, обладающей скоростью V = (V_x; V_y), вычисляется по формуле:

E = \frac{1}{2} m (V_x² + V_y²).

Евклидово расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле:

d(A, B) = √((x2 - x1)² + (y2 - y1)²).

Типовой пример организации данных во входном файле Три строки файла для трёх частиц:

0,67   -2,14   3,0    -4,0   0,2     V
3,14    7,22   3,2     4,3   0,7     II
1,33    5,56   0,00    5,22  0,456   IV

Для частицы из первой строки примера кинетическая энергия равна 2,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 = 2.0
cl = [[points[0]]]
for pt in points[1:]:
    if pt[2] - cl[-1][0][2] > R:
        cl.append([])
    cl[-1].append(pt)

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

Шаг 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 — расстояние между центрами

q1 = 10 ** 18
for i in range(len(centers)):
    for j in range(i + 1, len(centers)):
        q1 = min(q1, dist(centers[i], centers[j]))

Q1 — наименьшее евклидово расстояние между центрами двух различных кластеров.

Шаг 7. Q2 — среднее VII в «самом энергичном» кластере

max_pt = max(points, key=lambda q: q[2])
target = None
for cluster in cl:
    if max_pt in cluster:
        target = cluster
        break

vii = [p[2] for p in target if p[3] == "VII"]
q2 = sum(vii) / len(vii)

Находим частицу с наибольшей кинетической энергией во всём файле, берём её кластер и считаем среднее арифметическое энергий всех частиц с признаком VII в этом кластере.

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

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

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

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