分数: 600 点
问题陈述
给你多重集合 N 每个非负整数: A=\{ a_1,\ldots,a_N \} 和 B=\{ b_1,\ldots,b_N \}.
您可以按任意顺序执行以下操作任意次数。
- 选择一个非负整数 x in A。删除一个实例 x 来自 A 并添加一个实例 相反, 2x 。
- 选择一个非负整数 x in A。删除一个实例 x 来自 A 并添加一个实例 相反, \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 删除一个实例 相反, x\, (=3) 来自 A 并添加一个实例 相反, 2x\, (=6) 。现在我们有 A=\{4,5,6\}.
- 选择 x=5 删除一个实例 相反, x\, (=5) 来自 A 并添加一个实例 相反, \left\lfloor \frac{x}{2} \right\rfloor \, (=2) 。现在我们有 A=\{2,4,6\}.
示例输入 2
1 0 1
示例输出 2
-1
你不能转动 \{ 0 \} 进入 \{ 1 \} .