N-гиперпрямоугольник
(Время: 2 сек. Память: 256 Мб Сложность: 33%)
N-гиперпрямоугольник – это обобщение прямоугольника на N-мерном декартовом пространстве. Известно, что у N-гиперпрямоугольника всего 2N вершин (0-мерных граней) и N×2N-1 ребер (1-мерных граней). Например, для N=2 мы получим обычный прямоугольник с 4 вершинами и 4 ребрами (сторонами); а при N=3 это будет прямоугольный параллелепипед с 8 вершинами и 12 ребрами.
Задан N-гиперпрямоугольник с целочисленными координатами вершин и с ребрами, параллельными осям координат. Одна из его вершин находится в начале координат. Координата другой вершины (w1, w2, …, wN) определяет его размеры и является самой дальней координатой от начала координат.
Требуется осуществить обход всех вершин заданного N-гиперпрямоугольника по ребрам таким образом, чтобы при этом посетить каждую вершину ровно один раз. Формально, если (x1, x2, …, xN) и (y1, y2, …, yN) – две последовательные вершины в маршруте обхода, то должно выполняться следующее:
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 16) – размерность N-гиперпрямоугольника. Во второй строке записаны N целых чисел w1, w2, …, wN (1 ≤ wi ≤ 100) – координаты дальней вершины N-гиперпрямоугольника от начала координат.
Выходные данные
В выходной файл OUTPUT.TXT выведите 2N строк по N целых чисел в строке – последовательность обхода вершин в требуемом порядке. Если существует несколько возможных обходов, выведите любой.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1
3 | 0
3 |
| 2 | 2
5 7 | 5 0
0 0
0 7
5 7 |
Система оценки
Решения, работающие верно только для N ≤ 4, будут оцениваться в 25 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
