Задача g6_1008: Редкое имя. (castle.ssu.samara.ru/olymp/ - задача 1003)


Входной файл input.txt:
содержит список учащихся школы. В каждой строке через пробел заданы Фамилия
Имя и Отчество ученика. Требуется определить, какое имя самое редкое.
Число учеников в школе <= 10000.

Файл результата output.txt: содержит одну строку с искомым именем.

Пример input.txt:
Пушкин Александр Сергеевич
Луканов Александр Сергеевич
Соколова Любава Викторовна
Иванов Иван Иванович
Сидоров Иван Петрович

output.txt для данного примера
Любава

Решение g6_1008:
Эта задача была на втором туре областной олимпиады в Самарской области.
Не будем говорить, как из формата ФИО получить только имя, я надеюсь, что вы можете сделать это сами.
Я думаю, у этой задачи есть несколько решений, однако приведу свое, может быть слишком хитрое и запутанное для данной задачи, но все же верное, а также мои идеи по поводу несостоятельности некоторых других методов решения этой задачи.
Сначала я расскажу, что такое хэш-функция. Хэш-функция - это метод упорядочивания неупорядочиваемых (еле напечатал :) множеств. Звучит ужасно, но может быть будет понятно на примере.
Итак, я использовал хэш-функцию - функцию, которая по входной строке возвращает ее контрольную сумму, т.е. сумму кодов всех символов этой строки.
Для начала я создал массив из элементов word размер около 10000 элементов (хэш-функция от самого длинного русского имени наверняка в него поместится). Для ускорения работы я завел еще один массив такого же размера (о его предназначении позже).
После преобразования ФИО -> Имя -> Контрольная сумма мы увеличиваем значение элемента с номером, равным контрольной суммы, на 1 (мы используем позиционную хэш-функцию). Если до этого он был 0, то в другой массив заносим номер строки, где он встретился, чтобы в случае необходимости быстро найти его.
После того как мы прочитали весь файл мы ищем в нашем массиве минимальный ненулевой элемент, в другом массиве находим номер строки, в которой впервые встретилось это имя, читаем из нее ФИО и преобразовываем его в имя. Затем выводим его.
У меня еще была идея создать массив из строк string, который бы помещался в 64 кб. паскалевской памяти, а затем искать в нем самый редкий элемент, но при количестве имен 10000 длина строки была бы ограничена 5-ю символами, а в русском языке есть такие имена как Наталья и Наталия, Александр и Алексей и пр. в которых первые пять символов одинаковы, т.е. такое решение не было бы корректным(позже я просматривал тесты и думаю, что такое решение тоже бы прошло).
Конечно моя простенькая хэш-функция тоже могла завалиться, но шансы на это были гораздо меньше.
Скачать тесты к задаче