往届 ACM 队训练题 (参考)

1099. 最小向量点积

单点时限: 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
不限期开放

题目列表