ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102946
Тема:    [ Задачи с целыми числами ]
Сложность: 3-
Классы:
Название задачи: ХитрОе жюRи .
В корзину
Прислать комментарий

Условие

Дана последовательность целых чисел. Известно, что все числа в ней встречаются ровно два раза, кроме одного, которое встречается только один раз. Напишите программу, определяющую это число.

Входные данные

Входной двоичный файл содержит последовательность 32-битовых целых чисел со знаком (File Of LongInt).

Выходные данные

Выведите в выходной текстовый файл искомое число.

Пример входного файла

XXYYXYXYXXYY

Пример выходного файла

1498962264

Решение

Рассмотрим xor-сумму всех чисел, т.е. выражение a1 xor a2 xor ... xor an , где a1, a2, ..., an –числа, записанные во входном файле. Полученный результат будет равен искомому числу.

Действительно, a xor a = 0 и 0 xor a = a. В силу коммутативности и ассоциативности операции xor (проверьте эти свойства!) можно считать, что мы сначала выполнили xor тех чисел, которые встречаются дважды. В результате указанное выражение примет вид 

(b1 xor b1) xor (b2 xor b2) xor ... xor (bn div 2 xor bn div 2) xor с = с,

где bi – числа, которые встречаются в файле два раза, а c – один раз.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 6
Название Задачи на разные темы
Задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .