Виктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения 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 , то клавиатура считается полностью рабочей, поэтому численное значение коэффициента не имеет смысл. Формат входных данных Первая строка содержит натуральное число N ( 2 ≤ N ≤ 10 5 ) — число нажатий. Вторая строка содержит N натуральных чисел k i ( 1 ≤ k i ≤ 10 9 ) — номера нажатых клавиш. Третья строка содержит N натуральных чисел c i ( 1 ≤ c i ≤ 10 9 ) — коды соответствующих клавиш. Формат выходных данных Выведите значение коэффициента работоспособности клавиатуры, либо -1, если клавиатура полностью рабочая. Ответ будет засчитан, если его абсолютная или относительная погрешность не будет превышать 10 − 9 .

Ниже приведено подробное решение задачи с объяснениями и порядок действий. В конце — рабочая реализация на Python (посредством словаря). Формула коэффициента основана на вашем текстовом примере и на введённых вами подсказках: коэффициент равен sqrt(G) + sqrt(P) / ( sqrt(B) + sqrt(N) ), и если sqrt(B) + sqrt(N) = 0, то клавиатура считается полностью рабочей (выводим -1). 1) Что нужно посчитать - G: число хороших пар — пары с одинаковыми k и одинаковыми c. - P: число почти хороших пар — пары с различными k и различными c. - B: число плохих пар — пары с одинаковыми k, но разными c. - N: число почти плохих пар — пары с разными k, но одинаковыми c. 2) Как посчитать efficiently Обозначения: - freqK[k] — сколько нажатий имело номер клавиши k. - freqC[c] — сколько нажатий имело код c. - freqKC[(k,c)] — сколько раз встречается пара (k,c). Из них: - G = sum по всем (k,c): C(freqKC[k,c], 2) - Общее число пар T = C(N, 2) - A = sum по всем k: C(freqK[k], 2) — пары с одинаковым k (независимо от c) - B' = sum по всем c: C(freqC[c], 2) — пары с одинаковым c (независимо от k) - P = T - (A + B' - G) // по включению-исключению: исключаем пары, где ki==kj или ci==cj, но добавляем обратно те, что совпадают по обоим признакам (G) Для B и N: - Для каждого k: внутри группы одинакового k всего пар C(freqK[k], 2). Из них вычитаем пары с тем же (k,c): sum по c внутри этого k C(freqKC[k,c], 2). Значит B = sum_k [ C(freqK[k],2) - sum_c C(freqKC[k,c],2) ]. - Для каждого c: внутри группы одинакового c всего пар C(freqC[c], 2). Из них вычитаем пары с тем же (k,c): sum_k C(freqKC[k,c],2). Значит N (пусть назовём N_bad) = sum_c [ C(freqC[c],2) - sum_k C(freqKC[k,c],2) ]. 3) Пошаговый план вычисления - Построить: - freqK: словарь частот по k - freqC: словарь частот по c - freqKC: словарь частот по паре (k,c) - Вычислить: - G = sum over freqKC: v*(v-1)/2 - T = N*(N-1)/2 - A = sum over freqK: k*(k-1)/2 - Bp = sum over freqC: c*(c-1)/2 - P = T - (A + Bp - G) - Вычислить B: - Для каждого k посчитать s1[k] = sum по всем c, где (k,c) существует, C(freqKC[k,c],2) - B = sum_k C(freqK[k],2) - sum_k s1[k] - Вычислить N (назовём N_bad): - Для каждого c посчитать s2[c] = sum по всем k, где (k,c) существует, C(freqKC[k,c],2) - N_bad = sum_c [ C(freqC[c],2) - s2[c] ] - Проверить условие полной рабочей клавиатуры: если B = 0 и N_bad = 0, вывести -1. - Иначе вычислить: - denom = sqrt(B) + sqrt(N_bad) - ответ = sqrt(G) + sqrt(P) / denom - выдать с необходимой точностью (погрешность ≤ 1e-9) 4) Временная сложность - Все вычисления по словарям — в среднем O(N). - Дополнительные проходы по словарям зависят от числа различных ключей и пар, но суммарно не превышают O(N) по памяти и времени. 5) Пример кода (Python) ```python import math import sys from collections import defaultdict def solve(): data = sys.stdin.read().strip().split() if not data: return it = iter(data) N = int(next(it)) ks = [int(next(it)) for _ in range(N)] cs = [int(next(it)) for _ in range(N)] freqK = defaultdict(int) freqC = defaultdict(int) freqKC = defaultdict(int) for i in range(N): k = ks[i] c = cs[i] freqK[k] += 1 freqC[c] += 1 freqKC[(k, c)] += 1 # G: good pairs G = 0 for v in freqKC.values(): G += v * (v - 1) // 2 # Total pairs T = N * (N - 1) // 2 # A: pairs with same k A = 0 for v in freqK.values(): A += v * (v - 1) // 2 # B': pairs with same c Bp = 0 for v in freqC.values(): Bp += v * (v - 1) // 2 # P: almost good P = T - (A + Bp - G) # B: bad pairs (same k, different c) # sum_by_k_same_code[k] = sum over c of C(freqKC[k,c], 2) sum_by_k = defaultdict(int) for (k, c), m in freqKC.items(): sum_by_k[k] += m * (m - 1) // 2 B = 0 for k, nk in freqK.items(): B += nk * (nk - 1) // 2 B -= sum_by_k.get(k, 0) # N_bad: almost bad (same c, different k) sum_by_code = defaultdict(int) for (k, c), m in freqKC.items(): sum_by_code[c] += m * (m - 1) // 2 N_bad = 0 for c, nc in freqC.items(): N_bad += nc * (nc - 1) // 2 N_bad -= sum_by_code.get(c, 0) # If B + N_bad == 0 (i.e., sqrt(B) + sqrt(N_bad) == 0) if B == 0 and N_bad == 0: print(-1) return denom = math.sqrt(B) + math.sqrt(N_bad) # sqrt(P) is defined since P should be >= 0; but guard just in case if P < 0: P = 0 result = math.sqrt(G) + (math.sqrt(P) / denom) print("{:.12f}".format(result)) if __name__ == "__main__": solve() ``` 6) Пояснения по примерам и граничные случаи - Если все пары либо хорошие, либо почти хорошие, то B = 0 и N_bad = 0, и по условию выводится -1. - Все счетчики должны храниться в 64-битном диапазоне; в Python это автоматически, в C++ используйте int64_t. - Работа с большими N (до 1e5) реализована через хеш-таблицы; время примерно линейное, памяти требуется пропорционально числу различных k, c и пар (k,c). Если хотите, могу привести конкретный пример входных данных и пройти вручную по шагам подсчета G, P, B и N_bad.