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