Задача: Коды Грея
На занятиях по дискретной математике Сереже рассказали про двоичные коды Грея — это такое упорядочение всех 2n различных двоичных векторов длины n, что любые два соседних, а также первый и последний, вектора различаются ровно в одном разряде.
Для закрепления материала преподаватель задал им следующее задание: в коде Грея в каждом двоичном векторе ровно один бит заменен на знак вопроса «?». Требуется заменить обратно все знаки вопроса «?» на «0» или «1», чтобы получился код Грея.
Преподаватель обещал бонус на экзамене тому из студентов, кто первым справится с заданием. Помогите Сереже решить задачу или скажите, что это невозможно, и преподаватель задал нераз- решимое задание.
Формат входных данных
В первой строке содержится целое число n — длина двоичных векторов. Следующие 2n строк содержат двоичные вектора длины n, в каждом из которых ровно один символ заменен на знак вопроса «?».
Формат выходных данных
В первой строке выведите «YES», если решение существует, и «NO» — в противном случае. В случае положительного ответа выведите исходный код Грея, если возможных вариантов ответа несколько, выведите любой.
| Ввод |
Вывод |
2
0?
0?
1?
1? |
YES
00
01
11
10 |
3
?00
0?1
01?
0?0
?10
1?1
10?
1?1 |
NO |
Система оценки
| Номер подзадачи |
Баллы |
Ограничения |
Комментарии |
| 1 |
37 |
1<=n<=4 |
Баллы начисляются, если все тесты пройдены. |
| 2 |
63 |
1<=n<=12 |
Баллы начисляются, если все тесты этой и предыду- щих подзадач пройдены. |
Ваш ответ: