|
К коду Грея
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 2
0 1 3 2
2
1 2
2 1
| No
Yes |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
