Виктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения 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
, то клавиатура считается полностью рабочей, поэтому численное значение коэффициента не имеет смысл.
Ниже — подробное решение с пошаговыми объяснениями. Мы будем считать, что у Вас есть набор записей о нажатиях: каждый элемент это пара (ki, ci) — номер клавиши на самой клавиатуре и считанный её код.
1) Что нужно посчитать
- G — число хороших пар. Это количество пар (i, j) таких, что ki = kj и ci = cj.
- P — число почти хороших пар. Это пары, где ki ≠ kj и ci ≠ cj.
- B — число плохих пар. Это пары, где ki = kj и ci ≠ cj.
- N — число почти плохих пар. Это пары, где ki ≠ kj и ci = cj.
- Коэффициент K = (sqrt(G) + sqrt(P)) / (sqrt(B) + sqrt(N)).
- Если sqrt(B) + sqrt(N) = 0, клавиатура считается полностью рабочей и численное значение коэффициента не имеет смысла (то есть B = 0 и N = 0).
2) Как посчитать G, P, B, N
У Вас есть M записей: (k1, c1), (k2, c2), ..., (kM, cM). Рассматриваем все неупорядоченные пары между записями: для всех p < q сравниваем (kp, cp) и (kq, cq).
- Правило классификации для пары (kp, cp) и (kq, cq):
- если kp = kq и cp = cq → G++
- если kp ≠ kq и cp ≠ cq → P++
- если kp = kq и cp ≠ cq → B++
- если kp ≠ kq и cp = cq → N++
Практически, можно реализовать двумя способами.
Способ 1: прямой перебор всех пар (упрощённый, но медленный)
- Итерируем p от 1 до M-1, и q от p+1 до M.
- Выполняем классификацию по вышеуказанным условиям и считаем G, P, B, N.
- Сложность: O(M^2). годится для небольших данных.
Способ 2: через частоты (быстрый)
- Пусть:
- n_{ki, ci} — сколько раз встречается конкретная пара (ki, ci).
- n_k — сколько раз встречается конкретный номер клавиши ki (во всех кодах).
- n_c — сколько раз встречается конкретный код ci (для всех клавиш).
- Тогда:
- G = сумма по всем парам (ki, ci) от C(n_{ki,ci}, 2)
- B = сумма по всем клавишам ki от C(n_k, 2) минус сумма по всем парам (ki, ci) от C(n_{ki,ci}, 2)
- N = сумма по всем кодам ci от C(n_c, 2) минус сумма по всем парам (ki, ci) от C(n_{ki,ci}, 2)
- total_pairs = C(M, 2)
- P = total_pairs − (G + B + N)
Пояснение:
- G считает пары с тем же ki и тем же ci.
- B считает пары с тем же ki, но разными ci.
- N считает пары с тем же ci, но разными ki.
- P остаётся как все остальные пары, то есть пары с разными ki и разными ci.
Преимущество способа 2: можно посчитать за один проход по freq-словарям, без явного перебора всех пар. Это особенно полез для больших M.
3) Как посчитать коэффициент
- Если B = 0 и N = 0 (то есть sqrt(B) + sqrt(N) = 0), клавиатура полностью рабочая.
- Иначе применяем формулу:
K = (sqrt(G) + sqrt(P)) / (sqrt(B) + sqrt(N))
4) Пример
Предположим, у Вас есть такие записи (ki, ci):
1) (1, 10)
2) (1, 10) — повтор той же пары
3) (2, 20)
4) (3, 30)
5) (2, 25)
6) (4, 25)
M = 6. Всего пар = C(6, 2) = 15.
Вычислим через частоты:
- n_{1,10} = 2; n_{2,20} = 1; n_{3,30} = 1; n_{2,25} = 1; n_{4,25} = 1.
- n_k: n_1 = 2, n_2 = 2, n_3 = 1, n_4 = 1.
- n_c: n_{10} = 2, n_{20} = 1, n_{30} = 1, n_{25} = 2.
G = C(2,2) + ... = 1 (только (1,10) повторяет себя).
N:
- C(n_c, 2) суммируем по ci: C(2,2) + C(1,2) + C(1,2) + C(2,2) = 1 + 0 + 0 + 1 = 2
- C(n_{ki,ci}, 2) суммируем по парам: только (1,10) имеет 2 повторения → C(2,2) = 1
- N = 2 - 1 = 1
B:
- C(n_k, 2) суммируем по ki: C(2,2) + C(2,2) + C(1,2) + C(1,2) = 1 + 1 + 0 + 0 = 2
- C(n_{ki,ci}, 2) суммируем как выше: 1
- B = 2 - 1 = 1
P:
- total_pairs = 15
- P = 15 − (G + B + N) = 15 − (1 + 1 + 1) = 12
Коэффициент:
- sqrt(G) = 1
- sqrt(P) = sqrt(12) ≈ 3.464
- sqrt(B) = 1, sqrt(N) = 1 → сумма ≈ 2
- K ≈ (1 + 3.464) / 2 ≈ 2.232
Такой пример демонстрирует работу метода и полученные значения.
5) Быстрая реализация на Python (иллюстративно)
- Ниже простой каркас для вычисления G, P, B, N и коэффициента по списку пар (ki, ci).
def compute_coefficient(pairs):
import math
M = len(pairs)
if M < 2:
return None # недостаточно данных
from collections import Counter, defaultdict
# counts for (ki, ci), ki, ci
pair_counts = Counter(pairs) # n_{ki,ci}
n_k = Counter([k for (k, c) in pairs])
n_c = Counter([c for (k, c) in pairs])
# G
G = sum(v * (v - 1) // 2 for v in pair_counts.values())
# B
B = 0
for k, nk in n_k.items():
total_pairs_ki = nk * (nk - 1) // 2
inner = sum(pair_counts[(k, c)] * (pair_counts[(k, c)] - 1) // 2 for c in {cc for (kk, cc) in pair_counts if kk == k})
B += total_pairs_ki - inner
# Непосредственно можно посчитать N аналогично через ci
N = 0
for c, nc in n_c.items():
total_pairs_ci = nc * (nc - 1) // 2
inner = sum(pair_counts[(k, c)] * (pair_counts[(k, c)] - 1) // 2 for k in {kk for (kk, cc) in pair_counts if cc == c})
N += total_pairs_ci - inner
total_pairs = M * (M - 1) // 2
P = total_pairs - (G + B + N)
if (B ** 0.5) + (N ** 0.5) == 0:
return 'fully_working' # sqrt(B) + sqrt(N) = 0
K = (G ** 0.5 + P ** 0.5) / (B ** 0.5 + N ** 0.5)
return K
Пример использования:
pairs = [(1, 10), (1, 10), (2, 20), (3, 30), (2, 25), (4, 25)]
print(compute_coefficient(pairs))
# Вернёт приблизительно 2.232...
6) Важные замечания
- Если нет ни одной пары, или все пары попадают в одну из категорий, итог может быть нулевым/неопределённым. В частности, если B = 0 и N = 0, коэффициент не имеет смысла — клавиатура полностью рабочая.
- Для больших наборов пар эффективнее использовать способ через частоты (способ 2), чтобы избежать квадратичного перебора.
- В реальных тестах можно дополнительно проверить корректность классификации на тестовом наборе данных.
Если хотите, могу привести конкретный разбор вашего набора данных: пришлите список пар (ki, ci) или файл с ними — посчитаю G, P, B, N и коэффициент, покажу все промежуточные вычисления.
