• ХитрOе жюRи
  SLYXOR
  
  Условие  Комментарии  Решение  Тестовые файлы  Оглавление

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

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


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

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


Например:

SLYXOR.IN
XXYYXYXYXXYY

SLYXOR.OUT
1498962264





Идеи
Логическое исключающее ИЛИ и его свойства

Комментарии
Рассмотрим xor-сумму всех чисел, т.е. выражение a₁ xor a₂ xor...xor a_n , где a₁,a₂,...,a_n - числа, записанные во входном файле. Полученный результат будет равен искомому числу.

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

(b₁ xor b₁) xor (b₂ xor b₂) xor...xor (b_{n div 2} xor b_{n div 2}) xor с = с,

где b_i - числа, которые встречаются в файле два раза, а 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.

 

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