Виктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения 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 .

Ниже приводжу подробное решение задачи и готовый код. Введу все необходимые определения, тогда дам формулы и итоговый алгоритм, а затем пример реализации на языке Rust 1.56.

Цель задачи

• Посчитать коэффициент работоспособности клавиатуры по определениям:
  • Хорошая пара: k_i = k_j и c_i = c_j
  • Почти хорошая: k_i ≠ k_j и c_i ≠ c_j
  • Плохая: k_i = k_j и c_i ≠ c_j
  • Почти плохая: k_i ≠ k_j и c_i = c_j
• Обозначим:
  • G — число хороших пар
  • P — число почти хороших пар
  • B — число плохих пар
  • N — число почти плохих пар
• Коэффициент: (√G + √P) / (√B + √N)
• Если √B + √N = 0, клавиатура считается полностью рабочей и выводим -1.

Замечания по вычислениям

• Всего пар между N нажатиями: T = C(N, 2) = N(N-1)/2.
• Введём частоты:
  • freq_k[k] — сколько раз встречается номер клавиши k
  • freq_c[c] — сколько раз встречается код c
  • freq_kc[(k,c)] — сколько раз встречается пара (k, c)
• Вычислим нужные суммы:
  • G = sum over (k,c) of C(freq_kc[(k,c)], 2)
  • S_k = sum over k of C(freq_k[k], 2)
  • S_c = sum over c of C(freq_c[c], 2)
  • B = S_k - G
  • A = N-плохих? нет, Almost Bad — A = S_c - G
  • P = T - S_k - S_c + G
  • Примечание: A соответствует "почти плохим" и мы будем называть его A.

Проверки и вывод

• Если A == 0 и B == 0, выводим -1 (denominator равен нулю).
• Иначе вычисляем:
  • Gf = G, Pf = P, Af = A, Bf = B в виде f64
  • coef = (sqrt(Gf) + sqrt(Pf)) / (sqrt(Bf) + sqrt(Af))
• Выводим с достаточной точностью (например, 12 знаков после запятой).

Сложность

• Построение частот занимает O(N).
• Подсчёт G, S_k, S_c требует прохождения по элементам словарей, общая сложность O(N) ожидаемо.
• Память: O(U), где U — число уникальных значений k, уникальных c и уникальных пар (k,c). В рамках ограничений N ≤ 1e5.

Решение на Rust 1.56

use std::collections::HashMap;
use std::io::{self, Read};

fn main() {
    // Считываем вход
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let n: usize = it.next().unwrap().parse().unwrap();

    let mut ks: Vec<i64> = Vec::with_capacity(n);
    for _ in 0..n {
        let v: i64 = it.next().unwrap().parse().unwrap();
        ks.push(v);
    }

    let mut cs: Vec<i64> = Vec::with_capacity(n);
    for _ in 0..n {
        let v: i64 = it.next().unwrap().parse().unwrap();
        cs.push(v);
    }

    // Частоты
    let mut freq_k: HashMap<i64, u64> = HashMap::new();
    let mut freq_c: HashMap<i64, u64> = HashMap::new();
    let mut freq_kc: HashMap<(i64, i64), u64> = HashMap::new();

    for i in 0..n {
        *freq_k.entry(ks[i]).or_insert(0) += 1;
        *freq_c.entry(cs[i]).or_insert(0) += 1;
        let key = (ks[i], cs[i]);
        *freq_kc.entry(key).or_insert(0) += 1;
    }

    // G: количество пар с одинаковыми (k,c)
    let mut g: u128 = 0;
    for &f in freq_kc.values() {
        g += (f as u128) * ((f - 1) as u128) / 2;
    }

    // S_k: количество пар с одинаковым k
    let mut sk: u128 = 0;
    for &f in freq_k.values() {
        sk += (f as u128) * ((f - 1) as u128) / 2;
    }

    // S_c: количество пар с одинаковым c
    let mut sc: u128 = 0;
    for &f in freq_c.values() {
        sc += (f as u128) * ((f - 1) as u128) / 2;
    }

    let nn = n as u128;
    let t: u128 = nn * (nn - 1) / 2;

    // B = S_k - G
    let b: u128 = if sk >= g { sk - g } else { 0 };
    // A (almost bad) = S_c - G
    let a: u128 = if sc >= g { sc - g } else { 0 };

    // P = T - S_k - S_c + G
    let p_signed: i128 = (t as i128) - (sk as i128) - (sc as i128) + (g as i128);
    let p: u128 = if p_signed < 0 { 0 } else { p_signed as u128 };

    // Если denom равен нулю, клавиатура полностью рабочая
    if a == 0 && b == 0 {
        println!("-1");
        return;
    }

    // Вычисляем коэффициент
    let coef_numer = (g as f64).sqrt() + (p as f64).sqrt();
    let coef_denom = (b as f64).sqrt() + (a as f64).sqrt();

    let result = coef_numer / coef_denom;

    // Вывод с достаточной точностью
    println!("{:.12}", result);
}

Пояснение к коду

• Сначала строим три частотных отображения:
  • freq_k: сколько раз встречается каждый номер клавиши k
  • freq_c: сколько раз встречается каждый код c
  • freq_kc: сколько раз встречается конкретная пара (k, c)
• Затем вычисляем G, S_k, S_c по формулам C(x, 2) = x(x-1)/2.
• Находим B = S_k - G, A = S_c - G, P = T - S_k - S_c + G.
• Если A и B равны нулю, выводим -1. Иначе считаем коэффициент по формуле (√G + √P) / (√B + √A).

Как адаптировать под параметры задачи

• Если известны конкретные предметы или класс, стиль объяснения можно сделать более формальным и с примерами именно по данной теме (например, вероятности, комбинаторика, частоты).
• В данной реализации ориентирован на общую школьную задачу: объяснение шагов, затем решение и код.

Пример небольшого теста (для проверки)

• Пусть N = 4, пары (k,c): (1,10), (1,20), (2,10), (2,20)
  • freq_k: {1:2, 2:2} → S_k = C(2,2) + C(2,2) = 1+1 = 2
  • freq_c: {10:2, 20:2} → S_c = 2
  • freq_kc: each (k,c) appears once → G = 0
  • T = 6
  • B = S_k - G = 2
  • A = S_c - G = 2
  • P = T - S_k - S_c + G = 6 - 2 - 2 + 0 = 2
  • Denominator = sqrt(2) + sqrt(2) = 2*sqrt(2)
  • Numerator = sqrt(0) + sqrt(2) = sqrt(2)
  • coef = sqrt(2) / (2*sqrt(2)) = 1/2 = 0.5
• Код должен вывести примерно 0.5. Это можно проверить, запустив программу на этот тест.

Если нужно, могу адаптировать решение под другой язык или привести примеры с разбором конкретных чисел.