Задача 43:
Диски (castle.ssu.samara.ru/olymp/)
На полке имеются N коробок с CD-дисками. (1<=N<=100)
За 1 шаг можно либо снять любой из дисков с полки, либо поставить
его между любыми двумя другими, либо с любого края.
За какое минимальное число шагов можно переставить диски так, чтобы
в итоге все диски с одинаковой тематикой находились рядом?
input.txt:
название 1, тематика 1
...
название N, тематика N
output.txt:
K
где K - требуемое число шагов.
пример input.txt:
Web-Design 2000, web-дизайн
Quake III, игры
Windows 2000, софт
Коллекция клип-артов, web-дизайн
output.txt:
2
Решение:
Эта задача со второго тура Самарской областной олимпиады школьников
по программированию (
сервере областной олимпиады).
Итак, мы имеем набор строк с текстом, которые надо преобразовать во
что-нибудь более простое для обработки. Для этого используем мою
любимую хеш-функцию, считающую суммы ASCII кодов всех символов
слова, в данном случае это будет тематика диска.
Теперь у нас есть массив чисел, где количество чисел равно
количеству дисков. Теперь совершим над этим массивом преобразование,
похожее на сжатие RLE. Заведем два массива, один хранящий
хеш-функцию, а другой количество дисков одной тематики, идущих
подряд. Т.е.:
1, 1, 1, 2, 2, 1
преобразуется в два массива:
1, 2, 1
3, 2, 1
Теперь найдем самую часто встречающуюся тематику и самую большую
группу подряд идущих дисков этой тематики. А теперь начинается самое
интересное - то, до чего я дошел сам :).
Мы нашли самую большую группу и теперь будем двигаться в обе
стороны, ища группу таких же по тематике(самой частой!) дисков, при
этом будем считать, сколько дисков лежат между самой большой и этой
группой. Если количество дисков в группе меньше, чем количество
дисков между этой группой и максимальной, то возьмем все эти диски и
переложим к максимальной группе(обнулим значение количества дисков в
этой группе). На каждый диск уходит две операции. Если же количество
дисков в группе больше, то вынем все диски между этими
группами(обнулим значения счетчиков) и забудем об этих дисках (не
забыв прибавить к счетчику перестановок по 2 операции на каждый
диск), это значит, что мы одной операцией мы взяли диск, а второй
поставили куда душе угодно(куда надо).
Когда все наиболее часто встречающиеся диски будут сложены в одну
группу, заменим ее хеш-код на 0, например, чтобы функция поиска
наиболее часто встречающейся тематики не обрабатывала 0.
Теперь проведем проверку: если у всех дисков либо код тематики равен
0, либо длина последовательности подряд идущих дисков равна 0, то
пишем значение счетчика перестановок и выходим из программы. Иначе
повторяем с поиска самой частой тематике, пока не будет выполнено
условие выхода.
Как оказалось это еще не все, теперь идет еще интереснее: наш
читатель Axel нашел тест, на котором выше приведенное решение не
работает.
Мы нашли количество перестановок с помощью эвристического алгоритма,
однако это не всегда наименьшее количество. Теперь надо написать
рекрсивную процедуру, реализующую полный перебор. Это делается точно
также, (т.е. находим группу и идем от нее вправо-влево) но только мы
рассматриваем два варианта - удалить диски между группами или
перенести группу. При этом не забываем считать количество действие
и, в случае если оно превысило значение эвристически найденного или
текущего наименьшего в данный момент, то больше рекурсию не
запускаем. Это позволит отсечь большую часть ненужных веток и
ускорит полный перебор во много раз.
Далее
ð
