Зозуля для хешування#6648

Зозуля для хешування

1 секунда

64 мегабайти

Легка

Хеш-таблиця цілих чисел — це структура даних, яка дозволяє виконувати операції вставки, видалення та пошуку цілих чисел за постійний час. Зазвичай, хеш-таблиця складається з масиву певного розміру $n$ та хеш-функції $f (x)$ , яка часто визначається як $f (x) = x mod n$ f(x) = x \bmod n. Щоб вставити значення $x$ у таблицю, обчислюють його хеш-значення $f (x)$ , яке використовується як індекс у хеш-таблиці для зберігання $x$ . Наприклад, якщо $x = 1234$ x = 1234 і розмір хеш-таблиці $101$ , то $1234$ буде збережено на позиції $22 = 1234 mod 101$ 22 = 1234 \bmod 101. Можливо, що на позиції $22$ вже зберігається інше значення (наприклад, $x = 22$ x = 22), що призводить до колізії. Колізії можуть бути вирішені різними методами, які ви можете обговорити зі своїм науковим керівником по дорозі додому з конкурсу.

Зозуля-хешування — це метод хешування, який використовує дві хеш-таблиці $T_{1}$ T_1 та $T_{2}$ T_2, кожна з яких має свою хеш-функцію $f_{1} (x)$ f_1(x) та $f_{2} (x)$ f_2(x). Вставка значення $x$ відбувається так: спочатку намагаються зберегти $x$ у $T_{1}$ T_1 за допомогою $f_{1} (x)$ f_1(x). Якщо це місце порожнє, $x$ просто зберігається там, і процес завершено. Інакше виникає колізія, яку потрібно вирішити. Нехай $y$ — це значення, яке вже знаходиться в цьому місці. Ви замінюєте $y$ на $x$ у $T_{1}$ T_1, а потім намагаєтеся зберегти $y$ у $T_{2}$ T_2 за допомогою $f_{2} (y)$ f_2(y). Якщо це місце порожнє, ви зберігаєте $y$ там, і процес завершено. Інакше замінюєте значення там (назвемо його $z$ ) на $y$ , і тепер намагаєтеся зберегти $z$ назад у $T_{1}$ T_1 за допомогою $f_{1} (z)$ f_1(z), і так далі. Це продовжується, переміщуючись між двома таблицями, поки не знайдеться порожнє місце або не відбудеться певна кількість замін, після чого обидві таблиці перехешуються (це також можна обговорити зі своїм науковим керівником). Для цієї задачі, це останнє ніколи не станеться, тобто процес завжди триватиме, поки не буде знайдено порожнє місце, що гарантовано для кожного вставленого значення.

Зважаючи на розмір двох таблиць та серію вставок, ваше завдання — визначити, що зберігається в кожній з таблиць.

(Для тих, кого це цікавить, зозуля-хешування отримало свою назву від поведінки птаха зозулі, який відомий тим, що відкладає свої яйця в гнізда інших птахів разом з вже наявними яйцями. Коли більше пташеня зозулі вилуплюється, воно виштовхує інших пташенят з гнізда, таким чином отримуючи всю їжу для себе. Жахливо, але ефективно.)

Вхідні дані

Вхідні дані для кожного тестового випадку починаються з $3$ додатних цілих чисел $n_{1}$ n_1, $n_{2}$ n_2, $m$ , де $n_{1}$ n_1 та $n_{2}$ n_2 — це розміри таблиць $T_{1}$ T_1 та $T_{2}$ T_2 (з $n_{1}, n_{2} \leq 1000$ n_1, n_2 \leq 1000 та $n_{1} \neq = n_{2}$ n_1 \neq n_2), а $m$ — це кількість вставок. Після цього йтимуть $m$ цілих чисел, які є значеннями для вставки в таблиці. Усі ці значення будуть невід'ємними. Кожна таблиця спочатку порожня, і таблиця $T_{i}$ T_i використовує хеш-функцію $f_{i} (x) = x mod n_{i}$ f_i(x) = x \bmod n_i. Рядок, що містить $3$ нулі, завершить введення.

Вихідні дані

Для кожного тестового випадку виведіть непорожні позиції в $T_{1}$ T_1, а потім непорожні позиції в $T_{2}$ T_2. Використовуйте один рядок для кожної такої позиції у формі i:v, де $i$ — це індекс позиції в таблиці, а $v$ — це значення, яке там зберігається. Виводьте значення в кожній таблиці від найнижчого індексу до найвищого. Якщо будь-яка таблиця порожня, нічого не виводьте для цієї таблиці.

Приклади

Приклад 1