Maksymalne rzędy permutacji
Limit pamięci: 64 MB
Permutacją -elementową nazywamy różnowartościową funkcję
.
Rzędem permutacji nazywamy najmniejsze takie , że
dla wszystkich zachodzi:
Na przykład, rzędem trzyelementowej permutacji
jest 2, bo .
Dla zadanego rozważmy permutacje -elementowe o największym
możliwym rzędzie. Na przykład maksymalny rząd permutacji
pięcioelementowej wynosi 6. Przykładem permutacji pięcioelementowej,
której rząd wynosi 6 jest .
Spośród wszystkich permutacji -elementowych o maksymalnym rzędzie chcemy
znaleźć permutację najwcześniejszą (w porządku leksykograficznym). Dokładniej,
mówimy, że permutacja -elementowa
jest wcześniejsza niż permutacja -elementowa ,
gdy istnieje takie , że dla argumentów oraz .
Najwcześniejszą permutacją pięcioelementową o rzędzie 6 jest
.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia zestaw liczb całkowitych
,
-
dla każdej liczby (dla ) wyznaczy
najwcześniejszą -elementową permutację o maksymalnym rzędzie,
-
wypisze na standardowe wyjście wyznaczone permutacje.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się
jedna dodatnia liczba całkowita , .
W kolejnych wierszach znajdują się dodatnie liczby całkowite
, po jednej w wierszu,
.
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy.
Wiersz nr powinien zawierać ciąg liczb całkowitych oddzielonych spacjami,
będący ciągiem wartości
najwcześniejszej permutacji -elementowej o maksymalnym rzędzie.
Przykład
Dla danych wejściowych:
2
5
14
poprawną odpowiedzią jest:
2 1 4 5 3
2 3 1 5 6 7 4 9 10 11 12 13 14 8
Autor zadania: Jakub Pawlewicz.