Стоимость перемещений
Вас поставили во главе комиссии по инвентаризации Amalgamated Inc. AI имеет заводы в различных частях страны, каждый из которых производит различный набор продуктов. В настоящее время в каждом месте содержится вся линейка продуктов, которые содержатся в наборе складов, причем каждый склад хранит один тип продуктов. Вам следует переместить эти продукты между собой так, чтобы на складах они располагались в алфавитном порядке. Рассмотрим завод, который производит ксилофоны, q-элементы, дирижабли и скакалки и сохраняет их в четырех складах, как показано в верхней части следующего рисунка:
Стрелки показывают, как далеко каждый продукт должен быть перемещен, чтобы на складах они хранились в алфавитном порядке, который показан в нижней части на рисунке.
Менеджменту понравилась Ваша идея, однако он озабочен стоимостью перемещения всех продуктов. Чем дальше продукт должен быть перемещен, тем дороже это стоит, поэтому перед совершением перестановки менеджмент хотел бы знать общую длину, на которую все продукты должны быть перемещены для заданного места. На рисунке ксилофоны следует переместить на 2 склада, дирижабли на 1, а скакалки на 3, что суммарно стоит 6. Вам следует написать программу, которая определит стоимость перемещений автоматически.
Входные данные
Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей количество продуктов n в данном месте. Далее следует одна или несколько строк, содержащих n названий продуктов в их текущем расположении. Каждое название представляется строкой символов, пара соседних названий в каждой строке разделяется одним пробелом. Наибольшее значение n равно 1000, никакие два продукта не повторяются. Строка из одного нуля заканчивает ввод.
Выходные данные
Для каждого теста вывести номер места и общее количество перемещений, необходимых для реорганизации товаров. Следуйте приводимому формату.