Виктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения 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 , то клавиатура считается полностью рабочей, поэтому численное значение коэффициента не имеет смысл.
Ключевая идея и итоговая формула
- Коэффициент работоспособности клавиатуры равен (√G + √P) / (√B + √N).
- Если √B + √N = 0, то есть B = 0 и N = 0, клавиатура считается полностью рабочей и численное значение коэффициента не имеет смысла (даже можно сказать, что она идеально работает по этой модели).
Что такое G, P, B, N
- Вы анализируете все пары нажатий из записей Виктора. Пусть есть m нажатий, каждая запись — пара (k_i, c_i) — номер клавиши и зафиксированный код.
- Рассматриваете все пары i < j (все неупорядоченные пары двух нажатий).
- Для каждой пары сравниваете:
- ki = kj и ci = cj → Хорошая пара (Г): G++
- ki ≠ kj и ci ≠ cj → Почти хорошая пара (П): P++
- ki = kj и ci ≠ cj → Плохая пара (B): B++
- ki ≠ kj и ci = cj → Почти плохая пара (N): N++
Пошаговый алгоритм (для любой подходящей задачи)
- Соберите список всех нажатий: L = [(k1, c1), (k2, c2), ..., (km, cm)].
- Инициализируйте счетчики G = 0, P = 0, B = 0, N = 0.
- Для всех пар i = 1..m-1 и j = i+1..m:
- если ki = kj и ci = cj → G++
- else если ki ≠ kj и ci ≠ cj → P++
- else если ki = kj и ci ≠ cj → B++
- иначе (ki ≠ kj и ci = cj) → N++
- Посчитайте Den = √B + √N и Num = √G + √P.
- Если Den = 0, вывести: клавиатура полностью рабочая. Иначе вывести коэффициент = Num / Den.
Пример Допустим, у нас 4 нажатия:
- (k1=1, c1=10)
- (k2=2, c2=11)
- (k3=1, c3=10)
- (k4=3, c4=11)
Перебираем все пары (i < j):
- (1,2): ki≠kj и ci≠cj → П
- (1,3): ki=kj и ci=cj → Г
- (1,4): ki≠kj и ci≠cj → П
- (2,3): ki≠kj и ci≠cj → П
- (2,4): ki≠kj и ci=cj → Н
- (3,4): ki≠kj и ci≠cj → П
Итоги: G = 1, P = 4, B = 0, N = 1. Den = √0 + √1 = 1 Num = √1 + √4 = 1 + 2 = 3 Коэффициент = 3 / 1 = 3.0
Советы по практическому применению
- Безопасный способ подсчета G, P, B, N: используйте двойной цикл по всем парам i < j, или аккуратно агрегируйте подсчеты по группам (но в базовом варианте достаточно простого перебора).
- При больших данных можно искать оптимизации, например, хранить для каждого ключа и кода частоты, но базовый метод подходит для школьной задачи.
- Проверяйте условие Den = 0 отдельно, чтобы избежать деления на ноль.
Если хотите, можно привести ещё один пример на большем наборе данных или написать небольшой алгоритм/код (псевдокод) для автоматического подсчета в вашей задаче.
