7987: ABC254 —— Ex - Multiply or Divide by 2
[Creator : ]
Description
You are given multisets with N non-negative integers each: $A=\{a_1,…,a_N\}$ and $B=\{b_1,…,b_N\}$.
You can perform the operations below any number of times in any order.
jective 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.
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 $⌊\frac{x}{2}⌋$ instead. (⌊x⌋ is the greatest integer not exceeding x.)
Determine whether it is achievable, and find the minimum number of operations needed to achieve it if it is achievable.
Input
Input is given from Standard Input in the following format:
$N$
$a_1\ …\ a_N$
$b_1\ …\ b_N$
$N$
$a_1\ …\ a_N$
$b_1\ …\ b_N$
Output
If the objective is achievable, print the minimum number of operations needed to achieve it; otherwise, print -1.
Constraints
$1≤N≤10^5$
$0≤a_1≤…≤a_N≤10^9$
$0≤b_1≤…≤b_N≤10^9$
All values in input are integers.
$0≤a_1≤…≤a_N≤10^9$
$0≤b_1≤…≤b_N≤10^9$
All values in input are integers.
Sample 1 Input
3
3 4 5
2 4 6
Sample 1 Output
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 ⌊$\frac{x}{2}$⌋(=2) instead. Now we have A={2,4,6}.
Sample 2 Input
1
0
1
Sample 2 Output
-1
You cannot turn {0} into {1}.