AT_abc254_h [ABC254Ex] Multiply or Divide by 2

题目描述

给定两个由 $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$ 作为多重集完全相同。
请判断是否可以达成目标，如果可以，请求出所需操作次数的最小值。

输入格式

输入按以下格式从标准输入读入。

$N$ $a_1$ $\ldots$ $a_N$ $b_1$ $\ldots$ $b_N$

输出格式

如果可以达成目标，输出所需操作次数的最小值；否则输出 $-1$。

输入输出样例 #1

输入 #1

3
3 4 5
2 4 6

输出 #1

2

输入输出样例 #2

输入 #2

1
0
1

输出 #2

-1

说明/提示

限制条件

• $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$
• 输入均为整数

样例解释 1

可以通过如下两步操作达成目标：

• 选择 $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

无法将 $\{0\}$ 变为 $\{1\}$。

由 ChatGPT 4.1 翻译