I. Свидание

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


И Бог пообещал мужчине, что хороших и послушных жён
можно будет найти в любом уголке Земли. А потом
сделал Землю круглой… и смеялся, смеялся, смеялся.

Фольклор

Ни для кого не секрет, что студенты ОНУ лучше всех развлекаются в свободное время. И подарки они умеют выбирать со вкусом. Например, Антип Словоблудов, студент кафедры Мирового Господства, пригласил на свидание свою однокурсницу Илону Журнальчик и хочет подарить ей последовательность аж из 2∙N чисел. Чтобы не быть неправильно понятым и чтобы подарок не намекал на слишком близкие отношения, Антип хочет, чтобы любые два соседних числа этой последовательности различались как можно сильнее. Но вот незадача! В магазине, где ему продали эту последовательность, её тщательно отсортировали. Свидание под угрозой срыва. Пока Антипа успокаивают санитары, постарайтесь переупорядочить последовательность таким образом, чтобы минимальная разность двух соседних её элементов была максимальной.

Ввод. Первая строка ввода содержит число N (1 ≤ N ≤ 500). В следующей строке содержатся 2∙N элементов последовательности (от 1 до 1000000), расположенные по неубыванию и разделённые пробелами.

Вывод. Если максимально возможная минимальная разность соседних чисел превышает 1, в первой строке выведите её, а во второй – новую последовательность, разделённую пробелами. Если существует несколько верных последовательностей, выведите ту, которая больше понравится Илоне на ваш взгляд. Иначе выведите строку «Forever Ilona» без кавычек.

Идея – Артур Леонидович Максимов

Примеры

Входные данные Результат работы
2
1 2 3 10
2
1 3 10 2
2
1 2 2 10
Forever Ilona

Решение

Ниже Вы найдете несколько подсказок и текст решения задачи. Подсказки будут постепенно детализировать процесс решения. После чтения каждой подсказки желательно попытаться самому обдумать задача заново с учетом новой информации. Последовательность подсказок отражает последовательность "догадок" в процессе решения задачи. Конечно, это индивидуально. Т.е. я описываю как я размышлял над задачей, но не могу сказать, что это единственный путь.

Подсказка 1: Только не перебор! Select
Подсказка 2: Тасуем колоду Select
Подсказка 3: Переплетите пальцы Select
Решение на Java: Ok Select

Анализ

Решение оказалось очень простым. После того, как была нарисована картинка с идущим вверх графиком, изображающим исходную последовательность, сразу появился вариант Делим строго пополам и совмещаем две половинки. Но я с пессимизмом ждал от жизни подвоха!
Хотя я понял, что нужно выделить две последовательности, я посчитал, что одна может быть в середине, а другая составлена из оставшейся "приставки" и "окончания"! Т.е. я выделял наилучшие N элементов из середины и чередовал их со слитыми "приставкой" и "окончанием". В цикле выбирал лучшее положение "серединки". Причем еще и ухитрялся менять местами приставку и окончание и даже проверял четные и нечетные позиции для серединки.
Признаться это решение тоже прошло с первой попытки. Но первый вариант программы был почти втрое длиннее и работал на порядок (т.е. в N-раз) дольше чем окончательный.
Мораль? Больше оптимизма - короче код!

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

One thought on “I. Свидание

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