по времени 1 сек по памяти 256 Мб Аня любитель похихикать. Она даже придумала…
- User
по времени 1 сек по памяти 256 Мб
Аня любитель похихикать. Она даже придумала собственную оценку совместимости чувства юмора «хи-хи-хи», которая похожа на критерий хи-квадрат. Аня решила проверить, насколько её чувство юмора совместимо с Ваней.
Для этого она взяла сборник анекдотов и разбила их на несколько непересекающихся множеств. Также Аня предложила Ване разбить анекдоты на несколько непересекающихся множеств. Число множеств не обязательно должно быть одинаковым.
После этого оценка совместимости чувства юмора вычисляется по формуле: ∑A,B|o(A,B)−e(A,B)|e(A,B) где o(A,B) — реальное наблюдаемое число анекдотов, которые Аня отнесла к множеству A, а Ваня — к B, e(A,B) — ожидаемое число анекдотов, если предположить, что Аня и Ваня распределяют анекдоты по группам независимо друг от друга. При этом если e(A,B) равно нулю, то соответствующее слагаемое не учитывается. Замечание
В примере реальное число анекдотов выглядит как 12311202002, а ожидаемое число анекдотов 12310.61.21.220.40.80.8.
Аня отнесла к первому множеству три анекдота, а Ваня — один. Следовательно для Ани вероятность встретить анекдот из первого множества равна 3/5, а для Вани — 1/5. Совместная вероятность с учётом независимости равна 3/25, а математическое ожидание — 15/25. Максимальный балл за задачу - 100. Формат входных данных Первая строка содержит два натуральных числа M и K (1≤M,K≤105) — число множеств, на которые Аня и Ваня разбили анекдоты, соответственно. При этом некоторые множества могут быть пустыми. Вторая строка содержит натуральных число N (1≤N≤105) — число анекдотов в сборнике. Следующие N строк содержат по два натуральных числа ai и bi (1≤ai≤M, 1≤bi≤K) — номера множеств, к котором Аня и Ваня отнесли i-й анекдот. Формат выходных данных Выведите одно вещественное число с плавающей точкой — оценку совместимости чувства юмора «хи-хи-хи» между Аней и Ваней. Допустимая абсолютная и относительная погрешность 10−6. Пример 1 Входные данные
2 3 5 2 3 1 2 1 1 1 2 2 3
Выходные данные
5.833333333
- Assistant
To solve this problem, we need to compute the "хи-хи-хи" compatibility score between Anya and Vanya, given the way they classified jokes into categories. We'll break down the problem into several steps:
-
Data Collection: We'll read and store the input data, counting how many times each category appears for both Anya and Vanya.
-
Counting Observed Pairs: We'll count the number of times each combination of Anya's and Vanya's categories occurs.
-
Computing Expected Counts: For each observed pair, we'll compute the expected count assuming Anya's and Vanya's classifications are independent.
-
Calculating the Score:
- Observed Terms: For each observed pair, we'll compute the term (|o(A,B) - e(A,B)| / e(A,B)) and sum these up.
- Unobserved Terms: We'll calculate the number of category pairs that were not observed but have a non-zero expected count. Each of these contributes 1 to the total sum.
-
Summing Up: We'll sum the observed and unobserved terms to get the final score.
Here's the Python code that implements the solution:
import sys import threading def main(): import math import sys input = sys.stdin.readline M, K = map(int, sys.stdin.readline().split()) N = int(sys.stdin.readline()) sA = {} tB = {} o = {} for _ in range(N): ai, bi = map(int, sys.stdin.readline().split()) sA[ai] = sA.get(ai, 0) + 1 tB[bi] = tB.get(bi, 0) + 1 o_key = (ai, bi) o[o_key] = o.get(o_key, 0) +1 m = len(sA) k = len(tB) len_o = len(o) S0 = m * k - len_o N_float = float(N) s = 0.0 for (A, B), oAB in o.items(): sA_A = sA[A] tB_B = tB[B] eAB = sA_A * tB_B / N_float diff = abs(oAB - eAB) term = diff / eAB s += term total_S = s + S0 print("%.9f" % total_S) threading.Thread(target=main).start()Explanation:
-
Data Structures:
sA: A dictionary counting how many times Anya used each category.tB: A dictionary counting how many times Vanya used each category.o: A dictionary counting how many times each (Anya's category, Vanya's category) pair occurs.
-
Computing Expected Counts:
- For each observed pair
(A,B), the expected counteABis calculated as(sA[A] * tB[B]) / N.
- For each observed pair
-
Calculating the Score:
- Observed Terms: For each observed pair, we calculate the term and add it to
s. - Unobserved Terms: The number of unobserved terms is
S0 = m * k - len(o), wheremandkare the numbers of unique categories used by Anya and Vanya, respectively, andlen(o)is the number of observed pairs.
- Observed Terms: For each observed pair, we calculate the term and add it to
-
Output:
- We print the total score with nine decimal places, as required.
Note: The use of
threadingand definingmainis to ensure that the program doesn't exceed Python's recursion limit when processing large inputs. -