序列变换

发布时间: 2018年4月15日 22:34   最后更新: 2018年4月15日 23:25   时间限制: 2000ms   内存限制: 128M

给定两个长度为$n$的序列,$a_i, b_i$($1 \le i \le n$), 通过3种魔法使得序列a变换为序列b,也就是$a_i=b_i$($1 \le i \le n$).

魔法1: 交换$a_i$和$a_j$,$i \neq j$

首先通过若干次的魔法1将序列$a$变换成序列$c$

魔法2: 对1个数乘2或者加1

魔法3: 对1个数除以2或者减1,如果是奇数,则不能除以2

若$c_i>b_i$, 则只能对$c_i$实施魔法3,若$c_i<b_i$, 则只能对$c_i$实施魔法2. 例如$c_i=6$, $b_i=4$,

则可以通过对$c_i$实施2次减1操作(魔法3)将$c_i$变为$b_i$, 但不可以对$c_i$除以2再加1将$c_i$变为$b_i$,因为$c_i>b_i$, 所以不能对$c_i$实施加$1$操作(魔法2).

小埃想通过最少的操作次数使得序列$a$变成序列$b$, 操作次数是指使用的魔法次数。

输入测试组数$T$,每组数据,第一行输入$n$,$1 \le n \le 9$,紧接着输入两行,每行$n$个整数,前一行为$a_1,a_2,…,a_n$,后一行为$b_1,b_2,…,b_n$.其中$1 \le a_i,b_i \le 10^8$,$1 \le i \le n$.

每组数据输出一个整数,表示最少的操作次数

复制
2
2
8 7
5 1
4
4 3 1 3
1 1 4 3
6
3

2018

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛