images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
20/04/2024 05:33:38

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2104. Visit

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Little Mirko has paid a touristic visit to a village nearby Donji Andrijevci, a town in Slavonia. As it happens, the arrangement of streets in the village looks awfully familiar to the shape of a perfect binary tree of the order `K`. A perfect binary tree of order `K` consists of `2^K\ \ -\ 1` nodes arranged in `K` levels (just like in the image). Each node contains a building labeled with a house number. Moreover, all buildings but the ones in the last level have a left and right child (see the image again).
28733.png
Perfect binary tree of orders 2 and 3
Mirko has visited all the buildings in a village and noted down the exact entrance order. Now he wants to describe to you how the village looks like, but he can't quite remember. Luckily, he remembers the way in which he visited the buildings:
  • in the beginning, he was standing in front of the only building in the first level
  • if the building which he is currently standing in front of has a left child which he hasn't visited yet, he will move in front of the left child
  • if the building doesn't have a left child or he has already visited it, he will enter the current building and write its house number on his paper
  • if he has already visited the current building and the building has a right child, he will move in front of the right child
  • if he has visited the current building and its left and right child, he will return to the parent of the current building
After visiting the villages in the pictures above, the paper would look like this: 2-1-3 for the first village and 1-6-4-3-5-2-7 for the second village. Write a programme to help Mirko reconstruct the order of house numbers on each level.
The first line of input contains the integer `K` (`1\ ≤\ K\ ≤\ 10`), the number of levels of the village Mirko just visited.
The second line of input contains `2^K-1` integers, the sequence of house numbers on Mirko's paper. The house numbers will be unique and from the interval `[1,\ 2^K-1]`.
The output must consist of `K` lines. The `i`th line must contain the sequence of house numbers in the `i`th level of the village.

Sample Input #1

2
2 1 3

Sample Output #1

1
2 3

Sample Input #2

3
1 6 4 3 5 2 7

Sample Output #2

3
6 2
1 4 5 7
Clarification of the first and second example: The examples correspond to the images in the task.
Source: COCI 2013/2014, contest #5
loading