Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

К коду Грея

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

Рассмотрим циклическую последовательность попарно различных чисел {a0, a1, … , a2n-1}, 0 ≤ ai ≤ 2n-1. Назовем эту последовательность кодом Грея, если любой ai отличается от левого соседа ai-1 и правого соседа ai+1 только в одной цифре в двоичной записи этих чисел. Для a0 левым соседом считается a2n-1, а для a2n-1 правым соседом считается a0.

Вася хочет запрограммировать игру-головоломку, которая будет позволять пользователю менять местами два любых числа ai и aj . Задача игрока – получить код Грея. Модуль, отвечающий за перестановку чисел, Вася берет на себя. А вот Ваша задача – написать программу, которая будет определять после каждой перестановки – является ли последовательность кодом Грея.

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

В первой строке входного файла INPUT.TXT содержится число n. В следующей строке перечислены попарно различные числа ai. В третьей строке записано число m – количество перестановок, сделанных пользователем. В следующих m строках перечислены числа (i, j) – индексы переставляемых элементов. Ограничения: 1 ≤ n ≤ 16; 1 ≤ m ≤ 105; i≠j, 0 ≤ i, j < 2n.

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

В выходной файл OUTPUT.TXT запишите m строчек – в i-той строке запишите «Yes», если после i-той перестановки последовательность стала кодом Грея и «No» в противном случае.

Пример

INPUT.TXTOUTPUT.TXT
12
0 1 3 2
2
1 2
2 1
No
Yes

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

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483