Cuckoo for Hashing
Таблица хеширования целых чисел — это структура данных, которая позволяет вставлять, удалять и искать целые числа за постоянное время. Обычные хеш-структуры состоят из массива (собственно таблицы хеширования) определенного размера n и хеш-функции f(x), которая обычно задается как f(x) = x mod n. Чтобы вставить число x в таблицу, вычисляется его хеш-значение f(x), которое служит индексом в таблице для хранения x. Например, если x = 1234, а размер таблицы равен 101, то 1234 будет храниться в ячейке 22 = 1234 mod 101. Однако, если в ячейке 22 уже есть другое значение (например, x = 22), возникает коллизия. Коллизии можно решать разными способами, которые вы можете обсудить с вашим научным руководителем по дороге домой с конкурса.
Кукушкино хеширование — это метод, использующий две таблицы хеширования T_1 и T_2, каждая со своей хеш-функцией f_1(x) и f_2(x). Вставка числа x происходит так: сначала пытаемся разместить x в T_1 с помощью f_1(x). Если ячейка пуста, то просто сохраняем x там, и процесс завершен. В противном случае возникает коллизия, которую нужно разрешить. Пусть y — это значение, уже находящееся в этой ячейке. Мы заменяем y на x в T_1, а затем пытаемся сохранить y в T_2 с помощью f_2(y). Если это место пусто, сохраняем y там, и процесс завершен. В противном случае заменяем значение (назовем его z) на y, и теперь пытаемся сохранить z обратно в T_1 с помощью f_1(z), и так далее. Это продолжается, пока не найдется пустое место или не произойдет определенное количество замен, после чего выполняется повторное хеширование обеих таблиц (это также можно обсудить с вашим научным руководителем). Для этой задачи предполагается, что последнее событие никогда не произойдет, т.е. процесс всегда завершится нахождением пустого места, что гарантировано для каждого вставленного значения.
Учитывая размеры двух таблиц и последовательность вставок, ваша задача — определить, что хранится в каждой из таблиц.
(Для тех, кому интересно, кукушкино хеширование получило свое название от поведения птицы кукушки, которая известна тем, что откладывает свои яйца в гнезда других птиц. Когда вылупляется более крупный птенец кукушки, он выталкивает других птенцов из гнезда, получая всю пищу для себя. Жестоко, но эффективно.)
Входные данные
Ввод для каждого теста начинается с 3 положительных целых чисел n_1 n_2 m, где n_1 и n_2 — размеры таблиц T_1 и T_2 (при этом n_1, n_2 ≤ 1000 и n_1 ≠ n_2), а m — количество вставок. Далее следуют m целых значений, которые необходимо вставить в таблицы. Все эти значения будут неотрицательными. Каждая таблица изначально пуста, и таблица T_i использует хеш-функцию f_i(x) = x mod n_i. Строка, содержащая 3 нуля, завершит ввод.
Выходные данные
Для каждого теста выведите непустые ячейки в T_1, а затем непустые ячейки в T_2. Используйте одну строку для каждой такой ячейки в формате i:v, где i — это индекс ячейки в таблице, а v — значение, хранящееся там. Выводите значения в каждой таблице от наименьшего индекса к наибольшему. Если какая-либо таблица пуста, ничего для этой таблицы не выводите.