Виктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения OFF в ON, из-за этого Виктор уже заскучал. Но однажды ему принесли сломанную клавиатуру с неизвестной раскладкой. Виктор подключил клавиатуру к компьютеру и зашёл в текстовый редактор. Он стал нажимать различные клавиши из-за чего на экране в текстовом редакторе стали печататься неизвестные символы. Тогда Виктор использовал специальный анализатор, который напрямую считывает код нажатой клавиши, а также произвольно пронумеровал клавиши самой клавиатуры. Виктор решил, что хоть он и не знает правильной нумерации, всё равно можно оценить работоспособность клавиатуры. Для этого Виктор придумал численный коэффициент работоспособности клавиатуры. Для вычисления этого коэффициента Виктор нажимает произвольные клавиши на клавиатуре и записывает соответствующие полученные коды от анализатора. Так как правильное сопоставление неизвестно, то сравнивать номера и коды клавиш напрямую нельзя, поэтому Виктор решил анализировать нажатия попарно. Хорошей парой нажатий Виктор называет такую пару ( ( k i , c i ) i , ( k j , c j ) j ) , в которой совпадают и номера k i = k j , и коды c i = c j клавиш. Почти хорошая пара нажатий — пара ( ( k i , c i ) i , ( k j , c j ) j ) , в которой не совпадают и номера k i ≠ k j , и коды c i ≠ c j клавиш. Плохая пара нажатий — пара ( ( k i , c i ) i , ( k j , c j ) j ) , в которой совпадают номера k i = k j , но не совпадают коды c i ≠ c j клавиш. Почти плохая пара нажатий — пара ( ( k i , c i ) i , ( k j , c j ) j ) , в которой не совпадают номера k i ≠ k j , но совпадают коды c i = c j клавиш. Пусть G — число хороших пар нажатий клавиш, P — число почти хороших пар, B — число плохих пар, а N — число почти плохих пар. Тогда коэффициент работоспособности клавиатуры равен: √ G + √ P √ B + √ N Если √ B + √ N = 0 , то клавиатура считается полностью рабочей, поэтому численное значение коэффициента не имеет смысл. Напиши код на питоне

Ниже решение на Python с пошаговым объяснением и рабочим кодом. Что вычисляем - G: число хороших пар - P: число почти хороших пар - B: число плохих пар - N: число почти плохих пар Поскольку пара может быть любой из 4-х типов, общее число пар равно C(N_total, 2). Поэтому P = C(N_total, 2) - (G + B + N). Правила определения пары - Хорошая: ki == kj и ci == cj - Почти хорошая: ki != kj и ci != cj - Плохая: ki == kj и ci != cj - Почти плохая: ki != kj и ci == cj Алгоритм - Проходим по всем нажатиям и считаем: - nkc[(k, c)] — сколько раз пара (k, c) встречается - Tk[k] — сколько раз встречается конкретное k - Mc[c] — сколько раз встречается конкретное c - G: сумма C(nkc[(k,c)], 2) по всем (k, c) - B: для каждого k вычисляем C(Tk[k], 2) минус сумма C(nkc[(k,c)], 2) по всем c для данного k - N: для каждого кода c считаем C(Mc[c], 2) минус сумма C(nkc[(k,c)], 2) по всем k с этим c - P: общее число пар минус (G + B + N) - Коэффициент: sqrt(G) + sqrt(P) / ( sqrt(B) + sqrt(N) ), если sqrt(B) + sqrt(N) != 0. Если B = N = 0, коэффициент не имеет смысла — вернем 0.0 Сложность: O(n) по времени и памяти (где n — количество нажатий). Код (Python 3) ```python import sys import math from collections import defaultdict def main(): data = sys.stdin.read().strip().split() if not data: print("0.0") return it = iter(data) try: n = int(next(it)) except StopIteration: print("0.0") return nkc = defaultdict(int) # (k,c) -> count Tk = defaultdict(int) # k -> total count for this k Mc = defaultdict(int) # c -> total count for this code total_presses = 0 for _ in range(n): try: k = int(next(it)) c = int(next(it)) except StopIteration: break nkc[(k, c)] += 1 Tk[k] += 1 Mc[c] += 1 total_presses += 1 total_pairs = total_presses * (total_presses - 1) // 2 # G G = 0 for cnt in nkc.values(): if cnt >= 2: G += cnt * (cnt - 1) // 2 # B # sum_by_k[k] = sum over c of C(nkc[(k,c)], 2) sum_by_k = defaultdict(int) for (k, _), cnt in nkc.items(): if cnt >= 2: sum_by_k[k] += cnt * (cnt - 1) // 2 B = 0 for k, t in Tk.items(): total_k = t * (t - 1) // 2 B += total_k - sum_by_k.get(k, 0) # N # sum_by_code[c] = sum over k of C(nkc[(k,c)], 2) sum_by_code = defaultdict(int) for (k, c), cnt in nkc.items(): if cnt >= 2: sum_by_code[c] += cnt * (cnt - 1) // 2 N = 0 for c, m in Mc.items(): total_code_pairs = m * (m - 1) // 2 internal = sum_by_code.get(c, 0) N += total_code_pairs - internal P = total_pairs - (G + B + N) # Denominator for the division: sqrt(B) + sqrt(N) denom = math.sqrt(B) + math.sqrt(N) # Если B = N = 0, коэффициент не имеет смысла if denom == 0: print("0.0") return coef = math.sqrt(G) + (math.sqrt(P) / denom) # Вывод с разумной точностью print("{:.10f}".format(coef)) if __name__ == "__main__": main() ``` Пример использования - Вход (на примере, n = 5, пары (k,c)): 5 1 10 1 10 2 20 2 30 3 10 - Вывод будет рассчитан согласно приведенным формулам.