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

Задание
Напишите программу, определяющую число, встречающееся один раз


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

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


Например:

SLYXOR.IN
XXYYXYXYXXYY

SLYXOR.OUT
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 - один раз


 



Решение

{$A+,B-,D+,E-,F-,G+,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}

{$M 16384,0,655360}
 
program slyxor;
const base = 16128;
var f: file;
    s, fs, i, j: longint;
    q: array [0..Base] of longint;
begin
  s := 0;
  assign (f, 'slyxor.in'); reset (f, 4);
  fs := filesize(f);
  for i := 1 to fs div Base do
  begin
    BlockRead (f, q[1], Base);
    for j := 1 to Base do
      s := s xor q[j];
  end;
    BlockRead (f, q[1], fs mod Base);
    for j := 1 to fs mod Base do
      s := s xor q[j];
  close(f);
  assign (output, 'slyxor.out'); rewrite (output);
  writeln (s);
  close (output);
end.


 


© Особенности национальных задач по информатике