Score : $600$ points

问题陈述

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

您可以按照任意顺序执行以下操作任意次数：

• 从 $A$ 中选择一个非负整数 $x$。从 $A$ 中删除一个 $x$ 的实例，并添加一个 $2x$ 的实例。
• 从 $A$ 中选择一个非负整数 $x$。从 $A$ 中删除一个 $x$ 的实例，并添加一个 $\left\lfloor \frac{x}{2} \right\rfloor$ 的实例。（$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。）

您的目标是使 $A$ 和 $B$ 相等（作为多重集）。

确定这一目标是否可以实现，并在可实现的情况下找到实现所需的最小操作次数。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:50:50