XI Olimpiada Informatyczna 2003/2004
|
Zawody III stopnia |
Plik źródłowy: | mak.* |
Limit pamięci: | 64 MB |
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.
Spośród wszystkich permutacji n-elementowych o maksymalnym rzędzie chcemy
znaleźć permutację najwcześniejszą (w porządku leksykograficznym). Dokładniej,
mówimy, że permutacja n-elementowa
p jest wcześniejsza niż permutacja n-elementowa r,
gdy istnieje takie i, że p(j) = r(j) dla argumentów j < i oraz p(i) < r(i).
Najwcześniejszą permutacją pięcioelementową o rzędzie 6 jest
p(1)=2,p(2)=1,p(3)=4,p(4)=5,p(5)=3.
Napisz program, który:
W 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.
Twó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.
2 5 14poprawnym wynikiem jest:
2 1 4 5 3 2 3 1 5 6 7 4 9 10 11 12 13 14 8