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

Question

Задача Задача №3633856

А

Аноним

05 сентября 2026 11:27 · публичный вопрос

А

Аноним 05 сентября 2026 11:27

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

Запрос пользователя

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

Ответ нейросети

05 сентября 2026 11:27

Краткий ответ

Пусть:

\(S_k\) — число пар нажатий с одинаковыми номерами клавиш;
\(S_c\) — число пар с одинаковыми кодами;
\(G\) — число пар с одновременно одинаковыми номерами и кодами.

Тогда:

\[ B=S_k-G, \qquad N=S_c-G, \]

\[ P=\binom{n}{2}-S_k-S_c+G. \]

После этого вычисляем

\[ \frac{\sqrt G+\sqrt P}{\sqrt B+\sqrt N}. \]

Если \(B=N=0\), выводим \(-1\).

Почему это работает

Для группы из \(t\) одинаковых значений число пар внутри неё равно:

\[ \binom{t}{2}=\frac{t(t-1)}2. \]

Поэтому:

сортируем номера \(k_i\) и считаем пары одинаковых номеров;
сортируем коды \(c_i\) и считаем пары одинаковых кодов;
сортируем пары \((k_i,c_i)\) и считаем хорошие пары \(G\).

Почти хорошие пары — это пары, у которых различаются и номера, и коды. Из всех пар исключаем пары с одинаковым номером или одинаковым кодом:

\[ P=\binom{n}{2}-(G+B)-(G+N)+G =\binom{n}{2}-S_k-S_c+G. \]

Решение на C++17

#include <bits/stdc++.h>
using namespace std;

long long countEqualPairs(vector<long long> values) {
    sort(values.begin(), values.end());

    long long result = 0;
    int n = static_cast<int>(values.size());

    for (int i = 0; i < n; ) {
        int j = i + 1;
        while (j < n && values[j] == values[i]) {
            ++j;
        }

        long long cnt = j - i;
        result += cnt * (cnt - 1) / 2;
        i = j;
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> k(n), c(n);

    for (long long &x : k) {
        cin >> x;
    }
    for (long long &x : c) {
        cin >> x;
    }

    long long sameK = countEqualPairs(k);
    long long sameC = countEqualPairs(c);

    vector<pair<long long, long long>> both(n);
    for (int i = 0; i < n; ++i) {
        both[i] = {k[i], c[i]};
    }

    sort(both.begin(), both.end());

    long long good = 0;

    for (int i = 0; i < n; ) {
        int j = i + 1;
        while (j < n && both[j] == both[i]) {
            ++j;
        }

        long long cnt = j - i;
        good += cnt * (cnt - 1) / 2;
        i = j;
    }

    long long totalPairs = 1LL * n * (n - 1) / 2;

    long long bad = sameK - good;
    long long almostBad = sameC - good;
    long long almostGood = totalPairs - sameK - sameC + good;

    if (bad == 0 && almostBad == 0) {
        cout << -1 << '\n';
        return 0;
    }

    long double numerator =
        sqrtl(static_cast<long double>(good)) +
        sqrtl(static_cast<long double>(almostGood));

    long double denominator =
        sqrtl(static_cast<long double>(bad)) +
        sqrtl(static_cast<long double>(almostBad));

    long double answer = numerator / denominator;

    cout << fixed << setprecision(15) << answer << '\n';

    return 0;
}

Сложность решения:

\[ O(n\log n) \]

по времени и \(O(n)\) по памяти.

Краткий ответ

Почему это работает

Решение на C++17

Обсуждение