程序设计能力实训

1052. KL排序

单点时限: 2.0 sec

内存限制: 256 MB

一个随机变量 $x$ 可能取 $K$ 个值。在没有做实验时,我们事先给它的估计是均匀分布 $\frac{1}{K}$。在做 $M$ 次随机取值的实验之后,若取某个值 $i$ 的次数为 $L_i$,则该随机变量 $x$ 的分布记为 $p(x=i)=\frac{L_i+1/K}{M+1}$。

对于两个可以取同一组值的随机变量 $x$ 和 $y$,$y$ 到 $x$ 的 KL 散度表示为:

$$\sum_{i=1}^K p(x=i) \ln \frac{p(x=i)}{p(y=i)}$$

说明:$\ln$ 是以 $e$ 为底的对数。

现在有 $N+1$ 个随机变量 $x,y_1,\ldots,y_N$,并有它们在多次实验中取每个值的次数。请计算 $y_j$ $(j=1,2,3,\ldots,N)$ 到 $x$ 的 KL 散度值,散度值要求精确到小数点后4位。并根据 $y_j$ 到 $x$ 的KL散度由小到大对 $y_1,\ldots,y_N$ 进行排序。若散度值一样则以输入顺序排序。

输入格式

第 1 行:整数 $T(1 \leq T \leq 10)$ 为测试数据组数。
每组测试数据按照如下格式进行输入:
第 1 行:两个整数 $K$ 和 $N$ 的值,$2 \leq k \leq 10, 2 \leq N \leq 200$,$K$ 为随机变量可能的取值个数,$N$ 为待排序的随机变量个数。
第 2 行:$K$ 个整数,整数取值范围在 $[0,1000]$ 之间,表示 $x$ 在实验中取每个值的次数。
第 3~N+2 行:每行 $K$ 个整数,整数取值范围在 $[0,1000]$ 之间,表示待排序的随机变量 $y_j$ 在实验中取每个值的次数。按输入顺序 $j(j=1,\ldots,N)$ 是每个待排序随机变量的标号。

输出格式

对于每组测试数据,输出一行对应的编号(编号从 0 开始,格式:case #0: 等),然后接下来 $N$ 行输出排序的结果。每行输出一个整数和一个浮点数,分别是排序后的标号 $j$ 和对应的随机变量 $y_j$ 到 $x$ 的 KL 散度值,两个数之间以一个空格分隔,浮点数四舍五入到小数点后 4 位。

样例

Input
3
2 2
1 1
0 5
5 0
2 3
3 3
2 3
6 1
7 7
3 2
2 3 4
5 6 7
7 6 3
Output
case #0:
1 0.5928
2 0.5928
case #1:
3 0.0000
1 0.0141
2 0.2477
case #2:
1 0.0070
2 0.1632

提示

ln是以e为底的对数,C语言提供了标准库函数log计算以e为的对数。
函数原型:double log(double x);
头文件:<math.h>

在计算过程,请进行如下判断:
if(fabs(散度值)<1e-7) 散度值=0.0000;
浮点数的数据类型请定义为 double

对第三组测试数据的解释:

3 2  //K=3,N=2,随机变量可能的取值个数为3,待排序的随机变量个数为 2
2 3 4  //x在实验中取第一个值的次数为2,取第二个值的次数为3, 取第三个值的次数为4,实验次数M=9
5 6 7  //y1在实验中取第一个值的次数为5,取第二个值的次数为6,取第三个值的次数为7,实验次数M=18
7 6 3  //y2在实验中取第一个值的次数为7,取第二个值的次数为6,取第三个值的次数为3,实验次数M=16
不限期开放

题目列表