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

Ural SU contest. Petrozavodsk training camp. Winter 2008

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

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

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Старый Бильбо собирает песни и сказания всех народов Средиземья. Раз в двадцать лет он на год уезжает из Ривенделля, чтобы обойти за это время N городов Средиземья, пронумерованных числами от 1 до N (Ривенделль имеет номер 1), и в конце путешествия вернуться назад. Со времени последнего путешествия Бильбо прошло уже девятнадцать лет, и он понемногу начал собираться в дорогу. Из прошлого путешествия Бильбо помнит, что на входе в каждый город стоит стражник. Стражник спрашивает у путников, из какого города они пришли, и, в зависимости от этого, требует некоторую плату за вход в город. Времена меняются, и плата за проезд также меняется. Проконсультировашись с королём эльфов Эльрондом, Бильбо выяснил, что нынче за вход в город с номером A у тех, кто пришёл из города с номером B, стражники требуют ровно PA·[1000/PB] золотых, где Pi — население города с номером i, а [X] обозначает целую часть числа X. По мнению властей, такая плата стимулирует отток населения из крупных городов Средиземья в более мелкие. Бильбо знает население всех городов Средиземья и предполагает, что за год его путешествия население ни одного города не изменится. Как обычно, до начала путешествия ему хотелось бы найти такой порядок посещения городов, при котором потраченная сумма будет минимальна.

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

В первой строке целое число N. 2 ≤ N ≤ 1000. Во второй строке через пробел N целых чисел P1, …, PN — население городов Средиземья. Все Pi лежат в пределах от 1 до 1000.

Результат

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

Пример

исходные данныерезультат
4
10 3 5 4
1 4 2 3
Автор задачи: Александр Ипатов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2008
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1663. Хоббит или Туда и обратно 2