ABBYY Cup 2.0 - Hard |
---|
Закончено |
Умный Бобер из ABBYY имеет множество увлечений. Одно из них — это построение эффективных хеш-таблиц. Одной из самых серьезных проблем в хеш-таблицах является разрешение коллизий. Бобра очень заинтересовала эта проблема и он решил подробно ее исследовать.
Будем считать, что хеш-таблица состоит из h ячеек, пронумерованных от 0 до h - 1. В нее добавляются и из нее удаляются объекты. Каждый объект имеет свой уникальный идентификатор. Кроме этого, каждому объекту соответствует некоторое значение хеш-функции — целое число из отрезка от 0 до h - 1, включительно. Если при добавлении объекта ячейка, соответствующая значению хеш-функции объекта, свободна, то в нее помещается данный объект. В случае же, когда ячейка уже занята другим объектом, возникает коллизия. При удалении объекта из таблицы ячейка, в которую он был помещен, освобождается.
Умный Бобер недавно узнал о методе линейного пробирования для разрешения коллизий. Он заключается в следующем. Пусть значение хеш-функции для добавляемого объекта равно t и ячейка таблицы с номером t уже занята. Тогда мы пытаемся добавить этот элемент в ячейку (t + m) mod h. Если и она занята, то в ячейку (t + 2·m) mod h, затем в ячейку (t + 3·m) mod h и так далее. Заметим, что возможны ситуации, когда новый объект невозможно добавить в таблицу. Во входных данных для этой задачи гарантируется отсутствие таких ситуаций.
Операция a mod b обозначает взятие остатка от деления числа a на число b.
Данная методика сразу же показалась Бобру весьма неоптимальной и он решил оценить её неэффективность. Итак, вам дана последовательность операций добавления и удаления объектов из таблицы. При добавлении нового объекта происходит последовательность обращений к таблице. Каждое обращение к занятой ячейке таблицы будем называть холостым. Другими словами, если в результате алгоритма, описанного выше, объект добавился в ячейку (t + i·m) mod h (i ≥ 0), то произошло ровно i холостых обращений.
Требуется для данной последовательности операций добавления в таблицу и удаления из нее посчитать общее число холостых обращений к таблице. Будем считать, что при удалении некоторого объекта из таблицы не происходит холостых обращений. Также будем считать, что таблица перед выполнением операций пуста, то есть в ней нет ни одного объекта.
Первая строка входных данных содержит три целых числа h, m и n (1 ≤ m < h), разделенных пробелами, где h — размер хеш-таблицы, m — число, используемое для разрешения коллизий, n — количество операций.
В следующих n строках содержится описание операций. Порядок их выполнения соответствует порядку, в котором они следуют во входном файле. Каждая операция описывается одной строкой. Формат описания операций следующий:
Такой формат имеет операция добавления объекта в таблицу. Первый символ «+» (ASCII 43), затем следует единичный пробел, затем идентификатор объекта id (0 ≤ id ≤ 109), затем еще один пробел и значение хеш-функции для данного объекта hash (0 ≤ hash < h). Идентификатор объекта и значение хеш-функции для данного объекта являются целыми числами.
Такой формат имеет операция удаления объекта из таблицы. Первый символ «-» (ASCII 45), затем следует единичный пробел, затем идентификатор объекта id (0 ≤ id ≤ 109). Идентификатор объекта — целое число.
Гарантируется, что для всех операций добавления значение идентификатора является уникальным. Также гарантируется корректность исходных данных, то есть объект всегда возможно будет добавить в хеш-таблицу и не будет удалений несуществующих объектов.
Ограничения на входные данные для получения 20 баллов:
Ограничения на входные данные для получения 50 баллов:
Ограничения на входные данные для получения 100 баллов:
Выведите одно целое число — суммарное количество холостых обращений к хеш-таблице.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
10 2 7
+ 11 0
+ 22 2
+ 33 6
+ 44 0
+ 55 0
- 22
+ 66 0
7
5 1 6
+ 123 0
+ 234 1
+ 345 2
- 234
+ 456 0
+ 567 0
4
Название |
---|