Вартість переміщень#7387
Вас призначено головою комісії з інвентаризації компанії Amalgamated Inc. У Amalgamated Inc. є заводи в різних частинах країни, і кожен завод виробляє різний набір продуктів. На даний момент у кожному місці зберігається повний асортимент продуктів, розподілений по складах, причому кожен склад зберігає один тип продуктів. Ваше завдання — перемістити ці продукти так, щоб вони були розташовані на складах в алфавітному порядку. Наприклад, розглянемо завод, який виробляє ксилофони, q-елементи, дирижаблі та скакалки, і зберігає їх у чотирьох складах, як показано у верхній частині наступного рисунка:
Стрілки вказують, наскільки далеко кожен продукт потрібно перемістити, щоб вони були розташовані в алфавітному порядку, як показано в нижній частині рисунка.
Менеджменту сподобалася ваша ідея, але він стурбований вартістю переміщення всіх продуктів. Чим далі продукт потрібно перемістити, тим дорожче це коштує. Тому перед здійсненням перестановки менеджмент хотів би знати загальну відстань, на яку всі продукти повинні бути переміщені для заданого місця. На рисунку ксилофони слід перемістити на склади, дирижаблі на , а скакалки на , що сумарно коштує . Вам потрібно написати програму, яка автоматично визначить вартість переміщень.
Складаються з кількох тестів. Кожен тест починається з рядка, що містить кількість продуктів у даному місці. Далі йде один або кілька рядків, що містять назв продуктів у їх поточному розташуванні. Кожна назва представляється рядком символів, а сусідні назви в кожному рядку розділяються одним пробілом. Максимальне значення дорівнює , жодні два продукти не повторюються. Рядок з одного нуля завершує введення.
Для кожного тесту виведіть номер місця і загальну кількість переміщень, необхідних для реорганізації товарів. Дотримуйтесь наведеного формату.
Приклад 1