|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 17-4. Следующая...
(Разбор)
Задачу можно решать, получив по перестановке номер, увеличив его на 1, и сгенерировав перестановку по номеру, однако есть более простой и эффективный способ.
Пусть максимальный убывающий суффикс нашей перестановки имеет длину k. Тогда первые (n-k-1) позиций у следующей перестановки будут совпадать с текущей, на (n-k) месте будет стоять самое маленькое число, большее ak и не входящее в префикс длины (n-k-1), а остальные k чисел будут упорядочены по возрастанию. Отдельно следует рассмотреть случай, когда задана последняя перестановка.
Например, рассмотрим перестановку (6 1 5 3 10 9 8 7 4 2). Для нее k=6. Тогда первые 3 позиции в следующей перестановке будут равны 6,1 и 5. На 4 месте должно стоять число, большее 3 и не входящее во множество {6,1,5}. Такое число - 4. Остальные числа будут упорядоченны по возрастанию. Значит, следующая перестановка равна (6 1 5 4 2 3 7 8 9 10).