/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
(1, \dots, N) の順列 P = (P_1, \dots, P_N) が与えられます。ただし、(P_1, \dots, P_N) \neq (1, \dots, N) です。
(1 \dots, N) の順列を全て辞書順で小さい順に並べたとき、P が K 番目であるとします。辞書順で小さい方から K-1 番目の順列を求めてください。
順列とは？
(1, \dots, N) の順列とは、(1, \dots, N) を並べ替えて得られる数列のことをいいます。
辞書順とは？
長さ N の数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N) に対し、A が B より辞書順で真に小さいとは、ある整数 1 \leq i \leq N が存在して、下記の 2 つがともに成り立つことをいいます。
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i
制約
- 2 \leq N \leq 100
- 1 \leq P_i \leq N \, (1 \leq i \leq N)
- P_i \neq P_j \, (i \neq j)
- (P_1, \dots, P_N) \neq (1, \dots, N)
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 \ldots P_N
出力
求める順列を Q = (Q_1, \dots, Q_N) として、Q_1, \dots, Q_N をこの順に空白区切りで一行に出力せよ。
入力例 1
3 3 1 2
出力例 1
2 3 1
(1, 2, 3) の順列を辞書順で小さい順に並べると次のようになります。
- (1, 2, 3)
- (1, 3, 2)
- (2, 1, 3)
- (2, 3, 1)
- (3, 1, 2)
- (3, 2, 1)
よって P = (3, 1, 2) は小さい方から 5 番目であり、求める順列、すなわち小さい方から 5 - 1 = 4 番目の順列は (2, 3, 1) です。
入力例 2
10 9 8 6 5 10 3 1 2 4 7
出力例 2
9 8 6 5 10 2 7 4 3 1
Score : 300 points
Problem Statement
You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).
Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.
What are permutations?
A permutation of (1, \dots, N) is an arrangement of (1, \dots, N) into a sequence.
What is lexicographical order?
For sequences of length N, A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N), A is said to be strictly lexicographically smaller than B if and only if there is an integer 1 \leq i \leq N that satisfies both of the following.
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
- A_i < B_i.
Constraints
- 2 \leq N \leq 100
- 1 \leq P_i \leq N \, (1 \leq i \leq N)
- P_i \neq P_j \, (i \neq j)
- (P_1, \dots, P_N) \neq (1, \dots, N)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N P_1 \ldots P_N
Output
Let Q = (Q_1, \dots, Q_N) be the sought permutation. Print Q_1, \dots, Q_N in a single line in this order, separated by spaces.
Sample Input 1
3 3 1 2
Sample Output 1
2 3 1
Here are the permutations of (1, 2, 3) in ascending lexicographical order.
- (1, 2, 3)
- (1, 3, 2)
- (2, 1, 3)
- (2, 3, 1)
- (3, 1, 2)
- (3, 2, 1)
Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).
Sample Input 2
10 9 8 6 5 10 3 1 2 4 7
Sample Output 2
9 8 6 5 10 2 7 4 3 1