Сортування більярдних куль#3562
Обертання — це одна з популярних ігор у більярді. У ній використовуються куль, пронумерованих від до , які розташовуються, як показано на схемі на початку гри. (Примітка: порядок куль змінено від реальних правил Обертання для спрощення задачі.)
Ви — інженер, який розробляє автоматичну машину для більярду. На першому етапі вам потрібно було створити машину, яка встановлює початкову конфігурацію. Цей проект пройшов успішно, і нарешті була створена машина, яка могла розташувати кулі у трикутній формі. Однак, на жаль, вона не могла розмістити кулі в правильному порядку.
Тепер ви намагаєтеся створити іншу машину, яка виправляє порядок куль, обмінюючи їх. Щоб зменшити витрати, дозволено лише обмінювати кулю з її сусідніми кулями, які не знаходяться в тому ж рядку. Наприклад, у випадку нижче, можна обміняти лише такі пари: (,), (,), (,) та (,).
Напишіть програму, яка обчислює мінімальну кількість обмінів, необхідних для цього.
Перший рядок кожного тестового випадку містить ціле число (1 \le N \le 5), яке є кількістю рядків.
Наступні рядків описують, як кулі розташовані першою машиною; -й з них складається рівно з цілих чисел, які є номерами куль.
Введення завершується, коли N = 0. Ваша програма не повинна виводити для цього випадку.
Для кожного тестового випадку виведіть номер випадку та мінімальну кількість обмінів.
Ви можете припустити, що будь-яке розташування можна виправити не більше ніж за обмінів.
Приклад 1