реши задачу с помощью python 3.11. Виктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения OFF в ON, из-за этого Виктор…
Реши задачу с помощью python 3.11. Виктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения 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 .
Задача просит посчитать четыре количества пар между нажатиями клавиш и вывести коэффициент по формуле (sqrt(G) + sqrt(P)) / (sqrt(B) + sqrt(N)), где N в задаче — число почти плохих пар (назовём его N_ab, чтобы не путать с количеством нажатий).
Как считать без квадратичного перебора:
- G (хорошие пары): пары с одинаковыми k и одинаковыми c. G = sum по всем парам (k, c) от freq(k, c) выбиванию C(freq(k, c), 2).
- B (плохие пары): пары с одинаковым k, но разными c. B = sum по всем k C(freq(k), 2) minus G.
- N (почти плохие пары): пары с разными k, но одинаковыми c. N = sum по всем c C(freq(c), 2) minus G.
- P (почти хорошая пара): остальные пары, то есть P = total_pairs - G - B - N. total_pairs = C(N, 2).
После этого коэффициент
- если sqrt(B) + sqrt(N) = 0, выводим -1;
- иначе coef = (sqrt(G) + sqrt(P)) / (sqrt(B) + sqrt(N)).
Код на Python 3.11:
import sys
import math
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
if not data:
return
it = iter(data)
n = next(it)
ks = [next(it) for _ in range(n)]
cs = [next(it) for _ in range(n)]
# Подсчёт частот по k, по c и частот по паре (k, c)
freq_k = {}
freq_c = {}
freq_pair = {}
for k, c in zip(ks, cs):
freq_k[k] = freq_k.get(k, 0) + 1
freq_c[c] = freq_c.get(c, 0) + 1
key = (k, c)
freq_pair[key] = freq_pair.get(key, 0) + 1
# G: суммарное число пар с одинаковыми (k, c)
G = 0
for v in freq_pair.values():
if v >= 2:
G += v * (v - 1) // 2
# B: пары с одинаковым k, но разными c
sum_ck2 = 0
for v in freq_k.values():
if v >= 2:
sum_ck2 += v * (v - 1) // 2
B = sum_ck2 - G
# N_ab: пары с одинаковым c, но разными k
sum_cc2 = 0
for v in freq_c.values():
if v >= 2:
sum_cc2 += v * (v - 1) // 2
N_ab = sum_cc2 - G
total_pairs = n * (n - 1) // 2
P = total_pairs - G - B - N_ab
# Проверка на полностью рабочую клавиатуру
denom = math.sqrt(B) + math.sqrt(N_ab)
if denom == 0.0:
print(-1)
return
coef = (math.sqrt(G) + math.sqrt(P)) / denom
# Вывод с достаточной точностью
print(f"{coef:.12f}")
if __name__ == "__main__":
main()
Пояснения по использованию:
- Входные данные следует подать в том порядке, как в условии: N, затем N чисел ki, затем N чисел ci.
- Программа работает за O(N) времени и O(U) памяти, где U — число уникальных значений ki, ci и пар (ki, ci). Подход подходит для N до 1e5.
