3003. 最小向量点积

单点时限: 2.0 sec

内存限制: 256 MB

两个向量$a=[a_1,a_2, \cdots ,a_n]$ 和$b=[b_1,b_2, \cdots ,b_n]$ 的点积定义为 :

例如,两个三维向量 $[1, 3, -5]$ 和 $[4, -2, -1]$ 的点积是

假设允许对每个向量中的坐标值进行重新排列。找出所有排列中点积最小的一种排列,输出最小的那个点积值。

上例中的一种排列 $[3, 1 , -5]$ 和 $[-2, -1 , 4]$ 的点积为$-27$,这是最小的点积。

输入格式

第 $1$ 行:一个整数 $T$ ($1 \leqslant T \leqslant 10$) 为问题数。

接下来每个问题有 $3$ 行。第 $1$ 行是一个整数 $n$ $(1 \leqslant n \leqslant 1000)$,表示两个向量的维数。第$ 2$ 行和第 $3$ 行分别表示向量 $a$ 和向量 $b$。每个向量都有 $n$ 个由一个空格分隔的坐标值 $(-1000\leqslant 坐标值\leqslant 1000)$ 组成。

输出格式

对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0: 等)。

然后对应每个问题在一行中输出最小点积值。

样例

Input
3
3
3 1 -5
-2 -1 4
1
2
-298
5
1 2 3 4 5
1 0 1 0 1
Output
case #0:
-27
case #1:
-596
case #2:
6

1020 人解决,1078 人已尝试。

1290 份提交通过,共有 1936 份提交。

0.1 EMB 奖励。

创建: 7 年前.

修改: 1 年,9 月前.

最后提交: 4 天,9 小时前.

来源: 2013年编程实践课程非师范班第3次上机考试

题目标签