102547: [AtCoder]ABC254 Ex - Multiply or Divide by 2

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 \} $.

问题描述

给你两个包含$N$个非负整数的集合：$A=\{ a_1,\ldots,a_N \}$ 和 $B=\{ b_1,\ldots,b_N \}$。

• 从$A$中选择一个非负整数$x$，删除一个$x$的实例，并添加一个$2x$的实例。
• 从$A$中选择一个非负整数$x$，删除一个$x$的实例，并添加一个$\left\lfloor \frac{x}{2} \right\rfloor$的实例。 ($\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

你可以通过以下两种操作实现目标：

• 选择$x=3$，从$A$中删除一个$x\, (=3)$的实例，并添加一个$2x\, (=6)$的实例。现在我们有$A=\{4,5,6\}$。
• 选择$x=5$，从$A$中删除一个$x\, (=5)$的实例，并添加一个$\left\lfloor \frac{x}{2} \right\rfloor \, (=2)$的实例。现在我们有$A=\{2,4,6\}$。

样例输入2

1
0
1

样例输出2

-1

你不能将$\{ 0 \}$变成$\{ 1 \} $。