Задача g6_1044: Уникальная строка (отборочный тур на Самарскую областную олимпиаду 2000 г.)
Текстовый файл состоит из N строк (1 < N < 50000). Длина строки не превышает 255 символов. В этом файле есть строка, которая встречается один раз, все остальные строчки повторяются, причем четное количество раз. Необходимо найти эту уникальную строку (или иначе - исключить все повторяющиеся).
Входные данные:
Файл "US.IN" содержит строки. Список завершается "#". Этот символ находится отдельно, первым в последней строке и к списку не относится. Входные данные корректны, проверка на ошибки не требуется.
Выходные данные:
В файле "US.OUT" записывается уникальная строка.
Пример:
Файл "US.IN"
- Меня зовут Михаил, а Вас?
- Аваз.
- Меня зовут Михаил, а Вас?
- Аваз.
- Меня зовут...
#
Файл "US.OUT"
- Меня зовут...
Решение g6_1044:
Здорово я поизмачивался над этой задачей в свое время! Т.к. количество повторяющихся строк четно, то это неспроста. Здесь есть хитрость - а именно операция XOR (о ней более подробно можно прочитать в #1001 - Проблема с A и B).
Вот только единственная проблема - XOR можно делать только для строк одинаковой длины, но решается она просто - все строки дополняются каким-нибудь мусором до 255 символов (пробелы ставить не стоит - у жюри на таких умельцев есть тесты, я ставил рожицы улыбающиеся по Ctrl-B, а некоторые символ конца строки). Потом надо не забыть с конца строки срезать все эти символы, а то не поймут...
A xor B xor B xor C xor D xor C xor A = D - маленький пример