Задача H. Сортировка
Задачу добавил: alef
Успешно сдано решений: 13
Время на тест 2 с, память 256 Мб
Для отдела VVV приобретен новейший многопроцессорный компьютер. В этом компьютере аппаратно реализована операция реверсирования участка памяти. В результате у программистов появилась возможность реверсировать (задавать в обратном порядке) любое количество подряд идущих элементов одномерного массива методом reverse(n1, n2), где n1 – индекс левой границы, а n2 – индекс правой границы реверсируемого участка. Кеша заинтересовался возможностями новой операции применительно к сортировке одномерных массивов. Он сумел доказать, что для сортировки одномерного массива из N элементов необходимо не более N – 1 операции реверсирования, но не смог доказать, что данная оценка достижима (т.е., что для любого N существует такая исходная последовательность элементов, что отсортировать массив за число операций меньшее N – 1 невозможно).
Ваша задача — проверить второе утверждение экспериментально (хотя бы для небольших значений N) на массиве значений от 1 до N, т.е. определить все исходные состояния массива, для сортировки которых по возрастанию необходимо ровно N-1 операция реверсирования.
Формат входного файла input.txt
Первая строка — целое число N (2 ≤ N ≤ 8).
Формат выходного файла output.txt
Первая строка — целое число M — количество найденных исходных состояний массива, требующих для сортировки ровно N – 1 операций реверсирования.
В каждой из следующих M (если M > 0) строк — найденные исходные состояния массива (значения элементов массива выводятся через пробел), порядок вывода состояний может быть произвольным).
Пример входного файла
2
Пример выходного файла
1
2 1