← 返回题目列表

AtCoder · abc254_h

Ex. 乘以或除以 2

中文机器翻译题面 查看原题

分数: 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 \} .