Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Задача про XOR

(Время: 1 сек. Память: 16 Мб Сложность: 69%)

В рамках подготовки к чемпионату мира Кирилл придумал Ане задачу. Он написал N знаковых 32-битных чисел и попросил вычислить значение некоторого выражения S. Пусть a1, …, aN - все эти числа. Тогда выражение это

S = (a1 xor a2 xor … xor an) xor (b1 xor b2 xor … xor bn-1),

где

bi = F(ai, ai+1) xor F(ai, ai+2) xor … xor F(ai, an).

В этой формуле под знаком xor понимается побитовое «исключающее или», а F(a, b) = x - 1, где x - максимальная степень двойки, на которую делится нацело a-b, если a ≠ b, и F(a, b) = -1, если a = b. Все операции xor выполняются слева направо, если скобки не указывают иной порядок.

Аня, как большая специалистка в области циклов, быстро написала требуемую программу, однако программа работала слишком долго. Чтобы лучше разобраться в этом вопросе, она попросила вас написать программу, которая бы укладывалась в отведенное время. Помогите ей это сделать.

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

В первой строке входного файла INPUT.TXT содержится число N (1 ≤ N ≤ 105). В следующих N строках содержится N 32-битных знаковых целых чисел ai по одному на строке.

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

В выходной файл OUTPUT.TXT выведите значение выражения.

Примеры

INPUT.TXTOUTPUT.TXT
13
1
2
3
1
22
1
1
-1
33
1
2
4
6

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ