Аня любитель похихикать. Она даже придумала собственную оценку совместимости чувства юмора «хи-хи-хи», которая похожа на критерий хи-квадрат. Аня решила проверить, насколько её…
Аня любитель похихикать. Она даже придумала собственную оценку совместимости чувства юмора «хи-хи-хи», которая похожа на критерий хи-квадрат. Аня решила проверить, насколько её чувство юмора совместимо с Ваней. Для этого она взяла сборник анекдотов и разбила их на несколько непересекающихся множеств. Также Аня предложила Ване разбить анекдоты на несколько непересекающихся множеств. Число множеств не обязательно должно быть одинаковым. После этого оценка совместимости чувства юмора вычисляется по формуле: ∑ A , B | o ( A , B ) − e ( A , B ) | e ( A , B ) где o ( A , B ) — реальное наблюдаемое число анекдотов, которые Аня отнесла к множеству A , а Ваня — к B , e ( A , B ) — ожидаемое число анекдотов, если предположить, что Аня и Ваня распределяют анекдоты по группам независимо друг от друга. При этом если e ( A , B ) равно нулю, то соответствующее слагаемое не учитывается. Замечание В примере реальное число анекдотов выглядит как 1 2 3 1 1 2 0 2 0 0 2 , а ожидаемое число анекдотов 1 2 3 1 0.6 1.2 1.2 2 0.4 0.8 0.8 . Аня отнесла к первому множеству три анекдота, а Ваня — один. Следовательно для Ани вероятность встретить анекдот из первого множества равна 3 / 5 , а для Вани — 1 / 5 . Совместная вероятность с учётом независимости равна 3 / 25 , а математическое ожидание — 15 / 25 . Максимальный балл за задачу - 100. Формат входных данных Первая строка содержит два натуральных числа M и K ( 1 ≤ M , K ≤ 10 5 ) — число множеств, на которые Аня и Ваня разбили анекдоты, соответственно. При этом некоторые множества могут быть пустыми. Вторая строка содержит натуральных число N ( 1 ≤ N ≤ 10 5 ) — число анекдотов в сборнике. Следующие N строк содержат по два натуральных числа a i и b i ( 1 ≤ a i ≤ M , 1 ≤ b i ≤ K ) — номера множеств, к котором Аня и Ваня отнесли i -й анекдот. Формат выходных данных Выведите одно вещественное число с плавающей точкой — оценку совместимости чувства юмора «хи-хи-хи» между Аней и Ваней. Допустимая абсолютная и относительная погрешность 10 − 6 . Пример 1 Входные данные 2 3 5 2 3 1 2 1 1 1 2 2 3 Выходные данные
Чтобы решить задачу, необходимо вычислить оценку совместимости чувства юмора Ани и Вани с использованием предоставленных данных о анекдотах. Давайте поэтапно разберемся, как это сделать.
Шаги решения:
Чтение входных данных:
- Считываем количество множеств, на которые разбиты анекдоты Ани (M) и Вани (K).
- Считываем количество анекдотов (N).
- Считываем пары (ai, bi) для каждого анекдота, где ai - это множество Ани, а bi - множество Вани.
Подсчет наблюдаемых анекдотов:
- Создаем двумерный массив
O, гдеO[a][b]будет хранить количество анекдотов, отнесенных к множеству A (Ани) и множеству B (Вани).
- Создаем двумерный массив
Подсчет ожидаемых анекдотов:
- Для каждой группы A и B вычислим:
- Всего анекдотов в множестве A (количество анекдотов, отнесенных к A).
- Всего анекдотов в множестве B (количество анекдотов, отнесенных к B).
- Затем рассчитываем ожидаемое число анекдотов
E(A, B)с учетом независимости, используя формулу: \[ e(A, B) = \frac{N_A \cdot N_B}{N} \] где \(N_A\) — общее число анекдотов в группе A, \(N_B\) — общее число анекдотов в группе B, \(N\) — общее число анекдотов.
- Для каждой группы A и B вычислим:
Вычисление оценки совместимости:
- Используем формулу: \[ \text{оценка} = \sum_{A, B} \frac{|o(A, B) - e(A, B)|}{e(A, B)} \] Нужно учесть, что если \(e(A, B) = 0\), то данное слагаемое не учитывается.
Пример реализации:
Теперь давайте реализуем описанные шаги на Python, чтобы продемонстрировать вычисление:
def compatibility_score(M, K, N, anecdotes):
# Шаг 1: инициализируем матрицу наблюдаемых анекдотов
O = [[0] * (K + 1) for _ in range(M + 1)]
count_a = [0] * (M + 1) # Количество анекдотов в каждом множестве A
count_b = [0] * (K + 1) # Количество анекдотов в каждом множестве B
# Шаг 2: подсчитываем наблюдаемые анекдоты
for a, b in anecdotes:
O[a][b] += 1
count_a[a] += 1
count_b[b] += 1
total_anecdotes = N # Общее количество анекдотов
compatibility = 0.0
# Шаг 3: вычисляем оценку совместимости
for a in range(1, M + 1):
for b in range(1, K + 1):
observed = O[a][b]
expected = (count_a[a] * count_b[b]) / total_anecdotes if total_anecdotes > 0 else 0
if expected > 0:
compatibility += abs(observed - expected) / expected
return compatibility
# Входные данные
M, K = map(int, input().split())
N = int(input())
anecdotes = [tuple(map(int, input().split())) for _ in range(N)]
# Вычисляем оценку совместимости
result = compatibility_score(M, K, N, anecdotes)
# Выводим результат
print(f"{result:.8f}")
Примечание:
Этот код читает входные данные, подсчитывает наблюдаемые и ожидаемые значения, а затем вычисляет оценку совместимости и выводит ее с точностью до 8 знаков после запятой.
