Виктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения OFF в ON, из-за этого Виктор уже заскучал. Но однажды ему…

Ниже приведено подробное решение задачи с объяснениями и порядок действий. В конце — рабочая реализация на 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)

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.