|
Название задачи: Ожерелье. |
 |
Условие
|
Имя входного файла: |
necklace.in |
|
Имя выходного файла: |
necklace.out |
|
Максимальное время работы на одном тесте: |
1 секунда |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.
Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.
Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.
Формат входных данных
В первой строке входного файла записано число N (2 ≤ N ≤ 50).
Во второй строке через пробел следуют N различных чисел от 1 до N - номера колечек, расположенных вдоль нити по часовой стрелке.
Формат выходных данных
Выходной файл должен содержать описание процесса упорядочения.
В каждой строке, кроме последней, должны быть записаны через пробел два числа, указывающие номера колечек, протаскиваемых друг через друга. В последней строке должен стоять ноль.
Количество строк выходного файла не должно превышать 50000.
Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести одно число √1.
Пример
|
necklace.in |
necklace.out |
|
4 3 2 4 1 |
1 3 2 4 1 4 0 |
Также доступны документы в формате DOC
Решение
Тесты и проверяющая программа
Решения, написанные членами научного комитета и жюри Всероссийской олимпиады
Разбор задачи "Ожерелье"
Правильное решение
Задача всегда имеет решение. Достаточно с нужной стороны подогнать колечко N к колечку N-1, а дальше действовать рекурсивно, считая, что колечки N и N-1 склеены. Такое решение идейно простое, но не самое легкое для реализации, так как при протаскивании "склеенного колечка" необходимо делать сразу несколько перемещений.
Другое решение отдаленно напоминает метод сортировки пузырьком. Главное его преимущество заключается в том, что это решение очень легко придумать и запрограммировать. Кажется, что это решение не является верным, а представляет собой всего лишь некоторую эвристику, но доказать это не просто.
Решение заключается в том, что мы находим пару (x, y) соседних правильно упорядоченных колечек (x < y) таких, что их можно протащить друг через друга (|y-x| > 1), т.е. y-x > 1. Перетаскиваем колечки, ищем новую пару и так далее пока не получим полное упорядочивание колечек. Данное решение очень легко запрограммировать, но совершенно не понятно, почему оно всегда выдает правильный ответ.
Чтобы это понять, рассмотрим частный случай алгоритма: берем колечко с номером 1 и перемещаем его по часовой стрелке до тех пор, пока это возможно, т.е. пока не встретим колечко с номером 2. Затем аналогично перемещаем колечко с номером два, и так далее. В какой-то момент мы дойдем до последнего колечка. После этого повторяем проделанные операции заново и вновь пытаемся переместить колечко с номером 1. Интуитивно понятно, что в результате таких операций происходит постепенное упорядочивание колечек. Когда все колечки будут упорядочены по часовой стрелке, алгоритм завершит свое выполнение, так как ни одно из них невозможно будет переместить.
Докажем корректность работы алгоритма. Рассмотрим функцию Dist(x, y), которая возвращает расстояние от колечка x до колечка y, если двигаться по часовой стрелке. Дополнительно рассмотрим сумму S = 1xDist(1, 2)+ 2xDist(2, 3)+...+ nxDist(n, 1). Очевидно, что при смене колечек x и y местами в сумме S изменяются только слагаемые Dist(x, x+1) и Dist(y, y+1). Первое слагаемое при такой транспозиции увеличивается на 1, а второе - уменьшается на 1, значит, а вся сумма изменяется на величину ∆S = x-y. Учитывая, что x < y, получаем, что в результате перестановки колечек x и y сумма S уменьшается, а так как S все время остается положительным, то наш алгоритм рано или поздно закончит работу. Для завершения необходимо заметить, что в любой позиции, кроме правильного упорядочивания, существует "правильная" пара колечек, которые алгоритм должен поменять местами. Значит, после завершения работы алгоритма получится расстановка 1, 2, ..., N.
Можно доказать, что оба алгоритма выдают минимально возможное количество перестановок и в случае расположения колечек в обратном порядке общее количество транспозиций будет (N-2)(N-1)N/6. Получается, что верное решение задачи имеет кубическое время выполнения и линейный расход по памяти, а максимальное количество перестановок получается на тесте 50, 49, ..., 1 и равно 19600.
Эвристические решения и критерий их оценивания
Правильное решение набирает 100 баллов.
При небольших значениях N (N ≤ 11) верный ответ можно получить с помощью такого алгоритма: создаем граф, вершинами которого являются всевозможные конфигурации ожерелья. Затем при помощи поиска в ширину находим нужную последовательность транспозиций. Такое решение набирало 40-50 баллов.
Помимо этого оценивались решения, которые разбирали случаи маленьких значений N, прямой и обратный порядок расположения колечек и оценивалось примерно в 30 баллов. Решения, которые выдавали только 0 и -1 или проходили только тривиальные тесты на прямой порядок оценивались в 0 баллов.
Учитывая, что информация о номерах колечек хранится в массиве, можно было допустить ряд ошибок, связанных с тем, что массив - линейный объект, а ожерелье замкнуто и представляет циклическую структуру. Естественно такие решения проходили не все тесты и за счет ошибок реализации набирали меньшее количество баллов.
Также доступны документы в формате DOC
