ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Открытое личное первенство УрГУ 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Хоббит или Туда и обратно

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Старый Бильбо собирает песни и сказания всех народов Средиземья. С этой целью он хочет на год уехать из Ривенделля, обойти за это время N городов Средиземья, пронумерованных числами от 1 до N (Ривенделль имеет номер 1), и в конце путешествия вернуться назад. На входе в каждый город стоит стражник. Стражник спрашивает у путников, из какого города они пришли, и, в зависимости от этого, требует некоторую плату за вход в город. От мудрого короля эльфов Эльронда Бильбо узнал, что за вход в город с номером P у тех, кто пришёл из города с номером Q, стражник требует ровно PQ золотых. До начала путешествия хотелось бы найти такой порядок посещения городов, при котором потраченная сумма будет минимальна, а также такой, при котором она будет максимальна.

Исходные данные

Целое число N (2 ≤ N ≤ 50000).

Результат

В первой строке выведите N целых чисел — порядок посещения N городов, минимизирующий суммарную плату за вход. Во второй строке — аналогичный порядок, максимизирующий суммарную плату. Не забывайте, что Бильбо должен выйти из города с номером 1, побывать в каждом городе ровно по одному разу и только в конце путешествия вернуться в город с номером 1. Если у задачи существует множество решений, выведите любое из них.

Пример

исходные данныерезультат
4
1 4 2 3
1 3 4 2
Автор задачи: Александр Ипатов
Источник задачи: Восьмое открытое личное первенство УрГУ (3 марта 2007)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1535. Хоббит или Туда и обратно