XI Olympiad in Informatics 2003/2004
|
III stage competition (national finals) |
Source file: | mak.* |
Memory limit: | 64 MB |
A permutation of n elements is a one-to-one function (injection) p: {1,2,...,n} -> {1,2,...,n}. An order of permutation p is the minimal k >= 1, such that for all i=1,2,...,n we have:
, i.e. p composed with itself k times becomes identity function. For example, the order of the permutation of 3 elements
p(1)=3, p(2)=2, p(3)=1 is 2, because
p(p(1))=1, p(p(2))=2, p(p(3))=3.
For a given n let us consider permutations of n-elements having the
the largest order possible. For example, the maximal order of a permutation of 5 elements
is 6. An example of a permutation of 5 elements whose order is 6 is p(1)=4, p(2)=5, p(3)=2, p(4)=1, p(5)=3.
Among all permutations of n elements having the maximal order, we would like to find the earliest one
(in a lexycographic order). Being more precise,
we say a permutation p of n elements
is earlier than a permutation r of n elements,
if there is i, such that p(j) = r(j) for all j < i and p(i) < r(i).
The earliest permutation of 5 elements having an order 6 is
p(1)=2,p(2)=1,p(3)=4,p(4)=5,p(5)=3.
Write a programme that:
There is one positive integer d in the first line of the standard input, 1 <= d <= 10. In the following d lines there are positive integers n1, n2, ..., nd, one per line, 1 <= ni <= 10.000.
Your programme should write d lines to the standard output. The ith line should contain a sequence of integers separated by spaces, forming the least permutation of ni elements having the maximal order, i.e. the sequence p(1), p(2), ..., p(ni), where p denotes this permutation.
2 5 14the correct answer is:
2 1 4 5 3 2 3 1 5 6 7 4 9 10 11 12 13 14 8