@Mandy

Последовательность клеток занумерована числами от 1 до N. В каждой клетке стоит либо черная, либо белая фишка. Группой назовем набор подряд стоящих фишек одного цвета, ограниченный с обеих сторон фишками другого цвета или концами последовательности. Следует переместить фишки так, чтобы они образовали не более двух групп.
Перемещение фишек описывается с помощью плана обмена, в котором используются понятия операция обмена и шаг. Операция обмена меняет местами две соседние группы фишек. Шаг состоит не более чем из K одновременно выполняемых обменов. Обмены можно совершать одновременно только тогда, когда в них участвуют разные группы. После каждого шага группы одного цвета, оказавшиеся рядом, объединяются. План обменов содержит описания шагов, выполняемых последовательно.


Напишите программу, определяющую план обменов, с помощью которого за наименьшее число шагов получается последовательность, состоящая не более чем из двух групп.
Формат входных данных
В первой строке входного файла записаны числа N и K (1 <= N <= 100000 и 1 <= K <= 10000). Исходная расстановка фишек задается в последующих строках, содержащих N чисел (0 или 1), разделенных пробелами или переводами строк. При этом 0 соответствует черной фишке, 1 - белой.
Формат выходных данных
Выходной файл должен содержать описание шагов плана, по одному шагу на строке. Описание шага начинается с числа L - количества обменов на этом шаге. Затем для каждого обмена указывается минимальный номер клетки, в которой стоит фишка, участвующая в этом обмене. Последняя строка плана должна содержать одно число 0.
Примеры
fishes.in
9 3
1 0 0 1 1 0 1 1 0
fishes.out
2 1 6
1 1
0
fishes.in
3 1
1 1 0
fishes.out
0
Примечание
Требуется найти план, содержащий наименьшее число шагов, при этом общее число обменов может быть не минимальным.




Решение:

Заметим, что количество фишек в одной группе не имеет никакого значения, т.к. за один обмен мы из 3 или 4 групп получаем 2. Получается, что нам нужно хранить количество фишек в группе только для того, чтобы правильно выводить позицию, с которой начинается группа, участвующая в обмене.
Необходимо завести массив A от одного до N (т.к. все группы могут состоять из одного символа) и хранить в нем позицию, с которой начинаются символы i-ой группы. Это сделать несложно - читаем последовательно символы последовательности и если символ не равен предыдущему, то сохраняем в A[i] позиция, на которой находиться данный символ (отсюда начинается новая группа) и увеличиваем i. Общее количество групп обозначим за M.
Теперь необходимо разработать алгоритм перестановки групп, чтобы добиться желаемого эффекта за наименьшее количество шагов. Будем выполнять действия до тех пор, пока количество групп не станет равным 2. Наша последовательность представляет собой последовательность групп вида 010101. Разобьем нашу последовательность на тройки и в каждой тройке произведем обмен первого элемента со вторым и в итоге, для данного примера, получим последовательность 101, а на следующем шаге 01.
Определим количество операций обмена, которые мы совершим на данном шаге: оно равно минимуму из K и количеством троек, на которые можно разбить нашу последовательность. Обозначим его за C. Теперь мы будем совершать операции обмена, меняя в каждой тройке первый и второй элементы. Эти обмены необходимо совершать только в последних C тройках нашей последовательности, оставляя первые Z = M - C * 3 элементов неизменными.
Займемся обменами элементов в последних C тройках. Пусть j - элемент, с которого начинается изменение последовательности, j = M - C * 3 + 1. Теперь, перебирая все i от C до 1, выводим все A[q], где q = M - i * 3 + 1 (начало первой группы в тройке), вывод такого число обозначает, что мы поменяли группу q с группой q + 1, это значит, что объединились группы q - 1 и q + 1, а также группы q и q + 2. Необходимо внести соответствующее изменение в массив: A[j] := (A[q + 2] - A[q + 1]) + A[q], где (A[q + 2] - A[q + 1]) - длина последовательности q + 1, которая теперь встала перед q. После этого необходимо увеличить j на 1. Отдельно рассматривается случай, когда q = 1: здесь вместо четырех участвуют три группы и поэтому менять следует не первую группу со второй, а вторую с третьей, т.е. предварительно увеличить j на 1.
Такой, казалось бы, сложный и запутанный способ решения задачи избавляет нас от использования списков или многократного присваивания массивов. Надеюсь, при внимательном прочтении и рисовании возможных вариантов и последовательности действий на бумаге все станет понятно.



Вернуться к обсуждению:
Перемещение фишек C++

Миниатюры

 

0