Кассетная сортировка (ОКД НТИ 19/20 :: ИЭС)
Легенда
При работе с радиоэлектроникой приходится иметь рядом разные многочисленные детали, от больших микросхем и переключателей до SMD-резисторов и миниатюрных контактов. Чтобы содержать это разнообразие в порядке, человеческая мысль создала кассетницы — небольшой ящик с большим числом ячеек, которые можно занять всем, что туда помещается.
Одна из таких кассетниц стоит у программиста-радиоэлектронщика Саши Текстолитова, и в каждой её пронумерованной ячейке — какое-то количество радиодеталей одного вида.
Саша соблюдает порядок на рабочем столе, и, заметив во время очередной уборки, что ячейки в его кассетнице расположены беспорядочно, решил их отсортировать, переставив ячейки. Места на столе не так много, поэтому вытаскивать их можно лишь попарно, чтобы сразу поменять местами.
Саша решил, что хочет упорядочить ячейки кассетницы группами по убыванию суммарного числа деталей одного вида. То есть, сначала рядом встанут ячейки с деталями одного вида, которых у него больше всего, потом ячейки с меньшим общим числом деталей другого вида, и так далее. При этом порядок внутри самой группы не важен, как и порядок групп с равным числом деталей.
Обладая природно-программистской ленью, Саша хочет отсортировать кассетницу, сделав при этом минимальное число парных перестановок. Помогите ему составить инструкцию для сортировки. А чтобы вам было проще, Саша пронумеровал виды деталей.