|
Восстановление перестановки
(Время: 2 сек. Память: 16 Мб Сложность: 80%)
Знаменитая гипотеза Улама утверждает, что если рассмотреть граф G и построить мультимножество Gmin графов, получаемых из G удалением по очереди каждой из его вершин вместе со всеми инцидентными ей ребрами, то граф G можно однозначно восстановить по Gmin. Гипотеза Улама до сих пор не доказана, не известно и контрпримера.
В этой задаче мы рассмотрим аналогичную задачу для перестановок. Рассмотрим перестановку a = {a1, a2, ..., an} чисел от 1 до n. Обозначим как a/i перестановку n-1 чисел, полученных из a удалением числа i и уменьшением на единицу всех чисел, больших i. Например, если a = {1, 3, 5, 2, 6, 4}, то a/2 = {1, 2, 4, 5, 3}.
Вам заданы в некотором порядке перестановки a/1, a/2, ..., a/n. Требуется восстановить исходную перестановку a.
Входные данные
Первая строка входного файла INPUT.TXT содержит n – размер исходной перестановки (5 ≤ n ≤ 300). Следующие n строк содержат по n-1 числу каждая и задают a/i для всех i в некотором порядке.
Выходные данные
В выходной файл OUTPUT.TXT выведите n целых чисел – перестановку a. Гарантируется, что такая перестановка существует.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 6
1 3 5 2 4
1 3 4 2 5
1 2 4 5 3
2 4 1 5 3
1 4 2 5 3
1 3 2 5 4 | 1 3 5 2 6 4 |
Пояснение
В приведенном примере перестановки заданы в следующем порядке: a/6, a/4, a/2, a/1, a/3 и a/5.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |