|
|||||||||
|
Zadanie: MAK Maksymalne rzędy permutacji
Permutacją n-elementową nazywamy różnowartościową funkcję p: {1,2,...,n} -> {1,2,...,n}. Rzędem permutacji p nazywamy najmniejsze takie k >= 1, że dla wszystkich i=1,2,...,n zachodzi: Na przykład, rzędem trzyelementowej permutacji
p(1)=3, p(2)=2, p(3)=1 jest 2, bo
p(p(1))=1, p(p(2))=2, p(p(3))=3. Dla zadanego n rozważmy permutacje n-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 p(1)=4, p(2)=5, p(3)=2, p(4)=1, p(5)=3.
ZadanieNapisz program, który:
WejścieW pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita d, 1 <= d <= 10. W kolejnych d wierszach znajdują się dodatnie liczby całkowite n1, n2, ..., nd, po jednej w wierszu, 1 <= ni <= 10.000. WyjścieTwój program powinien wypisać na standardowe wyjście d wierszy. Wiersz nr i powinien zawierać ciąg liczb całkowitych oddzielonych spacjami, będący ciągiem wartości p(1), p(2), ..., p(ni) najwcześniejszej permutacji ni-elementowej o maksymalnym rzędzie. PrzykładDla danych wejciowych:2 5 14poprawnym wynikiem jest: 2 1 4 5 3 2 3 1 5 6 7 4 9 10 11 12 13 14 8 Wersja do druku |