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

Ниже решение на 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)

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
• Вывод будет рассчитан согласно приведенным формулам.