Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача 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



Задача H

Сдать задачу

Задать вопрос жюри по этой задаче