Вопрос от Анонимного юзера 04 октября 2025 06:51

Question 1

Реши задачу с помощью 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 .

Answer

Задача просит посчитать четыре количества пар между нажатиями клавиш и вывести коэффициент по формуле (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.

Question 2

реши задачу с помощью 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 .

Answer

Задача просит посчитать четыре количества пар между нажатиями клавиш и вывести коэффициент по формуле (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: ```python 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.

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

Задай свой вопрос

Похожие вопросы 15