Задача 22: Редкое
имя. (castle.ssu.samara.ru/olymp/ - задача 1003)
Входной файл input.txt: содержит
список учащихся школы. В каждой строке через пробел заданы Фамилия
Имя и Отчество ученика. Требуется определить, какое имя самое
редкое.
Число учеников в школе <= 10000.
Файл результата output.txt: содержит одну строку с искомым
именем.
Пример input.txt:
Пушкин Александр Сергеевич
Луканов Александр Сергеевич
Соколова Любава Викторовна
Иванов Иван Иванович
Сидоров Иван Петрович
output.txt для данного примера
Любава
Решение:
Эта задача была на втором туре областной олимпиады в Самарской
области.
Не будем говорить, как из формата ФИО получить только имя, я
надеюсь, что вы можете сделать это сами.
Я думаю, у этой задачи есть несколько решений, однако приведу свое,
может быть слишком хитрое и запутанное для данной задачи, но все же
верное, а также мои идеи по поводу несостоятельности некоторых
других методов решения этой задачи.
Сначала я расскажу, что такое хэш-функция. Хэш-функция - это метод
упорядочивания неупорядочиваемых (еле напечатал :) множеств. Звучит
ужасно, но может быть будет понятно на примере.
Итак, я использовал хэш-функцию - функцию, которая по входной строке
возвращает ее контрольную сумму, т.е. сумму кодов всех символов этой
строки.
Для начала я создал массив из элементов word размер около 10000
элементов (хэш-функция от самого длинного русского имени наверняка в
него поместится). Для ускорения работы я завел еще один массив
такого же размера (о его предназначении позже).
После преобразования ФИО -> Имя -> Контрольная сумма мы увеличиваем
значение элемента с номером, равным контрольной суммы, на 1 (мы
используем позиционную хэш-функцию). Если до этого он был 0, то в
другой массив заносим номер строки, где он встретился, чтобы в
случае необходимости быстро найти его.
После того как мы прочитали весь файл мы ищем в нашем массиве
минимальный ненулевой элемент, в другом массиве находим номер
строки, в которой впервые встретилось это имя, читаем из нее ФИО и
преобразовываем его в имя. Затем выводим его.
У меня еще была идея создать массив из строк string, который бы
помещался в 64 кб. паскалевской памяти, а затем искать в нем самый
редкий элемент, но при количестве имен 10000 длина строки была бы
ограничена 5-ю символами, а в русском языке есть такие имена как
Наталья и Наталия, Александр и Алексей и пр. в которых первые пять
символов одинаковы, т.е. такое решение не было бы корректным(позже я
просматривал тесты и думаю, что такое решение тоже бы прошло).
Конечно моя простенькая хэш-функция тоже могла завалиться, но шансы
на это были гораздо меньше.
Далее
ð
