/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 個の非負整数からなる多重集合 A=\{ a_1,\ldots,a_N \}, B=\{ b_1,\ldots,b_N \} が与えられます。
あなたは以下の操作を好きな順番で何度でも行えます。
- A に含まれている非負整数を 1 つ選び、x とする。 A から x を 1 つ削除し、代わりに 2x を 1 つ追加する。
- A に含まれている非負整数を 1 つ選び、x とする。 A から x を 1 つ削除し、代わりに \left\lfloor \frac{x}{2} \right\rfloor を 1 つ追加する。(\lfloor x \rfloor は x を超えない最大の整数)
あなたの目的は A と B を(多重集合として)一致させることです。
目的を達成することが出来るかどうかを判定し、出来る場合は必要な操作回数の最小値を求めてください。
制約
- 1 \leq N \leq 10^5
- 0 \leq a_1 \leq \ldots \leq a_N \leq 10^9
- 0 \leq b_1 \leq \ldots \leq b_N \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N b_1 \ldots b_N
出力
目的を達成出来る場合は必要な操作回数の最小値を出力せよ。出来ない場合は -1 を出力せよ。
入力例 1
3 3 4 5 2 4 6
出力例 1
2
次のようにして 2 回の操作で目的を達成できます。
- x=3 とし、A から x\, (=3) を 1 つ削除し代わりに 2x\, (=6) を 1 つ追加する。これによって A=\{4,5,6\} となる。
- x=5 とし、A から x\, (=5) を 1 つ削除し代わりに \left\lfloor \frac{x}{2} \right\rfloor \, (=2) を 1 つ追加する。これによって A=\{2,4,6\} となる。
入力例 2
1 0 1
出力例 2
-1
\{ 0 \} を \{ 1 \} にすることは出来ません。
Score : 600 points
Problem Statement
You are given multisets with N non-negative integers each: A=\{ a_1,\ldots,a_N \} and B=\{ b_1,\ldots,b_N \}.
You can perform the operations below any number of times in any order.
- Choose a non-negative integer x in A. Delete one instance of x from A and add one instance of 2x instead.
- Choose a non-negative integer x in A. Delete one instance of x from A and add one instance of \left\lfloor \frac{x}{2} \right\rfloor instead. (\lfloor x \rfloor is the greatest integer not exceeding x.)
Your objective is to make A and B equal (as multisets).
Determine whether it is achievable, and find the minimum number of operations needed to achieve it if it is achievable.
Constraints
- 1 \leq N \leq 10^5
- 0 \leq a_1 \leq \ldots \leq a_N \leq 10^9
- 0 \leq b_1 \leq \ldots \leq b_N \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 \ldots a_N b_1 \ldots b_N
Output
If the objective is achievable, print the minimum number of operations needed to achieve it; otherwise, print -1.
Sample Input 1
3 3 4 5 2 4 6
Sample Output 1
2
You can achieve the objective in two operations as follows.
- Choose x=3 to delete one instance of x\, (=3) from A and add one instance of 2x\, (=6) instead. Now we have A=\{4,5,6\}.
- Choose x=5 to delete one instance of x\, (=5) from A and add one instance of \left\lfloor \frac{x}{2} \right\rfloor \, (=2) instead. Now we have A=\{2,4,6\}.
Sample Input 2
1 0 1
Sample Output 2
-1
You cannot turn \{ 0 \} into \{ 1 \} .