시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 10 | 6 | 3 | 60.000% |
1 ∼ NまでのN個の数字の順列A1, A2, ……, ANが与えられる。 この順列に対して区間[i, j](1 ≤ i ≤ j ≤ N)の数字の順序を逆順にする操作reverse(i, j)を行うことが出来る。 例えば、[1, 2, 3, 4, 5]に対してreverse(2, 4)を適用すると[1, 4, 3, 2, 5]となる。 最小で何回の操作を行えば順列を昇順にソートされた状態にすることが出来るか計算せよ。
入力は以下の形式で与えられる。
N A1 A2 …… AN
問題の解を1行に出力せよ。
Nは整数である
2 ≤ N ≤ 10
5 1 4 3 5 2
2
reverse(4,5):1 4 3 2 5
reverse(2,4):1 2 3 4 5
のようにすればよい。
5 3 1 5 2 4
4
reverse(1,2):1 3 5 2 4
reverse(3,5):1 3 4 2 5
reverse(2,4):1 2 4 3 5
reverse(3,4):1 2 3 4 5
のようにすればよい。
3 1 2 3
0
10 3 1 5 2 7 4 9 6 10 8
9