Polish version    English version  
  Historia OI -> XI OI 2003/2004 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: MAK

Maksymalne rzędy permutacji

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.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia zestaw liczb całkowitych n1,n2,...,nd,
  • dla każdej liczby ni (dla i=1,2,...,d) wyznaczy najwcześniejszą ni-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 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ście

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.

Przykład

Dla danych wejœciowych:
2
5
14
poprawnym wynikiem jest:
2 1 4 5 3
2 3 1 5 6 7 4 9 10 11 12 13 14 8



Wersja do druku