Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Восстановление перестановки

(Время: 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.TXTOUTPUT.TXT
16
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.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 A. Окружность
 B. Прямоугольный многоугольник
 C. Наименьшее общее кратное
 D. Геометрическая головоломка
 E. Магический квадрат
 F. Восстановление перестановки
 G. Хорошая таблица
 H. Деление столбиком

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru



Оценочная компания Россия - оценка Оценочная компания.