H. Подумаешь, коммивояжёр!

Ограничение времени: 2 с
Ограничение памяти: 256 M

У, параллельные, ну как вы достали меня!
Валерий Меладзе

Ни для кого не секрет, что студенты ОНУ с лёгкостью решают NP-полные задачи. Даже первокурсник способен без труда в уме найти максимальную клику в графе при помощи только лишь циркуля и линейки. Поэтому, чтобы не заставлять студентов скучать на паре, преподаватели вынуждены всячески усложнять общеизвестные NP-полные задачи. Хотите хотя бы на пару часов почувствовать себя первокурсником ОНУ? Тогда попробуйте решить вот такую задачу:

В вершинах правильного N-угольника расположены N городов. Требуется посетить их все ровно один раз и вернуться в исходный город. Перемещаться можно только по диагоналям и сторонам многоугольника. При этом требуется, чтобы среди всех возможных маршрутов выбранный маршрут имел максимальную длину. Чтобы задача не показалась Вам чересчур простой, дополнительно потребуем, чтобы никакие два отрезка маршрута не были параллельны друг другу.

Ввод. Единственная строка ввода содержит натуральное число N (3 ≤ N ≤ 42) – количество городов, которые требуется посетить.

Вывод. Если Вы не можете найти требуемый обход, выведите строку «Sorry, I am from ITMO» без кавычек. Иначе выведите N вершин в порядке обхода, разделяя их пробелами. Если требуемых обходов несколько, выведите Ваш любимый.

Идея – Роман Игоревич Чепляка
и Олег Александрович Петров

Примеры

Входные данные Результат работы
3
2 1 3
4
Sorry, I am from ITMO
About the post author Igor Mazurok (5 Posts)

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine KBIS Software Developer

Author Info

Igor Mazurok

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine
KBIS Software Developer

Добавить комментарий