Pascal ABC

 

ГЛАВНАЯ
ССЫЛКИ
ОЛИМПИАДНЫЕ ЗАДАНИЯ
Очень простые

Проблема с A и B

Трамвайные билеты

Шифр Цезаря

Четные и нечетные члены последовательности

"Мы вас упакуем!"

Простые

Равновеликие прямоугольники

Скобки

 

Уравнение

 

Вирусы

 

КВН

 

Коррекция кода

 

Степень

 

Демократия в опасности

 

Пуговицы

 

A to B

 

Палиндромы

 

Почти Крэг Туми

 

Виза

 

Ездец

 
Средней сложности  

MIME64

 

Куль хацкеры

 

Редкое имя

 

Города

 

Исправления

 

Банки

 

2^n

 

Ниточка

 

Массивище

 

Знакомые

 

Считаем кораблики

Лошадью ходи!

Левые повороты

Прицельное метание помидор

Анаграммы

Треугольник

Принцип компании

Уникальная строка

Конфуз

K-ичные числа

Михаил Густокашин против бюрократии

Агенты

Игра в слова

Сложные

Диски

Домино

Монеты

Программистика

Хитрющая строка

Робот-сапер

Квадраты

Упаковка простых

Оппозиция

 

Замок

 

Многоугольники

 

Электронные часы

 

Дождик

 

Черепаха

 

Метро

 

Террористы

 

Школы

 
Очень сложные/особо интересные  

Система Защиты

 

Бизнес-классики

 

Телеметрия

 

Лесной пожар

 

Олимпиада

 

Автобусный диспетчер

 

 Кубики

 

Электронная почта

 

Автобус

 

 

 

 

ОЛИМПИАДНЫЕ ЗАДАНИЯ

Олимпиадные задачи с рекомендациями к решениям

Задача 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 - маленький пример

Далее ð





 


 

 

 
 

СЕРВИС

Copyright © 2008 СОШ №2 им. Н.П. Массонова г.Свислочь © Синица А.А.