03/04/2025 15:39:16

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2761. Сравнение хеш-таблиц

Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Определить максимальное количество сравнений ключей и среднее количество сравнений при успешном поиске (суммарное количество сравнений ключей для каждого ключа в таблице, деленное на количество ключей) для unordered_set и хеш-таблицы с открытой адресацией после заполнения таблицы заданными $N$ значениями.

Обе структуры должны иметь одинаковый заданный размер $M$ ( $M>N$ ). В unordered_set размер указывается в конструкторе как первый аргумент.

Количество сравнений в unordered_set можно вычислить $sum_{i=0}^(M-1) k_i*(k_i+1)//2$ , где $k_i$ это $"bucket_size"(i)$

В хеш-таблице добавить в метод find(T key) подсчет количества сравнений в глобальной переменной.

Первая строка ввода содержит два целых числа $N$ и $M$ , вторая строка – $N$ целых чисел.

В первой строке вывести максимальное количество сравнений ключей и среднее количество сравнений при успешном поиске в unordered_set. Во второй – аналогичные значения для хеш-таблицы с открытой адресацией.

Пример ввода

10 19
1 2 3 4 10 20 100 101 1000 1001

Пример вывода

2 1.100000
3 1.200000