/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
N 枚のカードがあり、1, 2, ..., N の番号がついています。 カード i (1 \leq i \leq N) の片方の面には赤い文字で整数 A_i が、 もう片方の面には青い文字で整数 B_i が書かれています。 最初、これらのカードは赤い文字が書かれた面を表にして 左から右に番号順に一列に並んでいます。
以下の操作を繰り返すことで、カードの表側の面に書かれた整数の列が左から右に広義単調増加となる （すなわち、各 i (1 \leq i \leq N - 1) に対して、左から i + 1 枚目のカードの表側の面に書かれた整数が i 枚目のカードの表側の面に書かれた整数以上である） ようにすることが可能かどうか判定してください。 さらに、可能である場合、必要な操作の回数の最小値を求めてください。
- 整数 i (1 \leq i \leq N - 1) を一つ選ぶ。 左から i 番目のカードと i + 1 番目のカードの位置を入れ替え、さらにこれら 2 枚のカードを裏返す。
制約
- 1 \leq N \leq 18
- 1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N B_1 B_2 ... B_N
出力
単調増加となるようにすることが不可能である場合、-1 と出力せよ。
可能である場合、必要な操作の回数の最小値を出力せよ。
入力例 1
3 3 4 3 3 2 3
出力例 1
1
i = 1 として操作を 1 回行うと、 カードの表側の面に書かれた整数の列は [2, 3, 3] となり、単調増加となります。
入力例 2
2 2 1 1 2
出力例 2
-1
何回操作を行っても、 カードの表側の面に書かれた整数の列は [2, 1] のままであり、これは単調増加ではありません。
入力例 3
4 1 2 3 4 5 6 7 8
出力例 3
0
操作を行う必要がない場合もあります。
入力例 4
5 28 15 22 43 31 20 22 43 33 32
出力例 4
-1
入力例 5
5 4 46 6 38 43 33 15 18 27 37
出力例 5
3
Score : 700 points
Problem Statement
We have N cards numbered 1, 2, ..., N. Card i (1 \leq i \leq N) has an integer A_i written in red ink on one side and an integer B_i written in blue ink on the other side. Initially, these cards are arranged from left to right in the order from Card 1 to Card N, with the red numbers facing up.
Determine whether it is possible to have a non-decreasing sequence facing up from left to right (that is, for each i (1 \leq i \leq N - 1), the integer facing up on the (i+1)-th card from the left is not less than the integer facing up on the i-th card from the left) by repeating the operation below. If the answer is yes, find the minimum number of operations required to achieve it.
- Choose an integer i (1 \leq i \leq N - 1). Swap the i-th and (i+1)-th cards from the left, then flip these two cards.
Constraints
- 1 \leq N \leq 18
- 1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N B_1 B_2 ... B_N
Output
If it is impossible to have a non-decreasing sequence, print -1.
If it is possible, print the minimum number of operations required to achieve it.
Sample Input 1
3 3 4 3 3 2 3
Sample Output 1
1
By doing the operation once with i = 1, we have a sequence [2, 3, 3] facing up, which is non-decreasing.
Sample Input 2
2 2 1 1 2
Sample Output 2
-1
After any number of operations, we have the sequence [2, 1] facing up, which is not non-decreasing.
Sample Input 3
4 1 2 3 4 5 6 7 8
Sample Output 3
0
No operation may be required.
Sample Input 4
5 28 15 22 43 31 20 22 43 33 32
Sample Output 4
-1
Sample Input 5
5 4 46 6 38 43 33 15 18 27 37
Sample Output 5
3