Problem 1082 --Buddy

1082: Buddy

Time Limit: 3 Sec  Memory Limit: 64 MB
Submit: 20  Solved: 8
[Submit][Status][Web Board][Creator:]

Description

gungun 正在学习关于 OS(操作系统)的知识,了解到有一种神奇的内存管理算法叫做 Buddy System(伙伴系统)。

如果您了解伙伴系统,可以跳过下面两个段落以节省时间。

Buddy System 把系统中的可用存储空间划分为存储块(Block)来进行管理,每个存储块的大小必须是2的n次幂,即1,2,4,8,16,32,64,128等等。假设系统全部可用空间为2^k,那么在 Buddy System 初始化时将生成一个长度为k+1的可用空间表List,并将全部可用空间作为一个大小为2^k的块挂接在List的最后一个节点上,如下图:

当收到x个字节的内存请求时,Buddy System分配的内存大小总是2^m个字节(满足2^(m-1)<x<=2^m)。Buddy System将在List中的m位置寻找可用的Block。显然List中这个位置为空,于是Buddy System就开始不断向下查找m+1,m+2,直到找到不为空的位置,也就是刚才说的k。找到k后,便得到可用Block(k),此时Block(k)将分裂成两个大小为2^(k-1)的块,并将其中一个插入到List中k-1的位置,同时对另外一个继续进行分裂。如此以往,直到得到两个大小为2^m的块为止,并将其中一个分配(离开了可用空间表)。分配后的List如下图所示:

可以发现,Buddy System在分配存储块时经常会将一个大的存储块分裂成两个大小相等的小块,那么这两个小块就称为“伙伴”。比如在上面的一次分配过程中,就产生了k-m次的“伙伴”。

zyyyyy也觉得上述过程非常地神奇!他很想知道在响应n个内存请求的过程中,至少会产生多少次“伙伴”。本题中假定这些请求均同时到达,并且不考虑释放。

gungun知道这其实就是将n个请求任意排序,求最小的分裂次数。但是 gungun 的作业实在太多了,只能请你帮帮忙,赶紧求出来打发 zyyyyy

Input

第一行一个整数T,表示数据组数。

在每组数据中,第一行两个整数n k,分别表示内存请求条数,总的内存量为2^k;第二行n个整数ai,表示每个请求需要多大的内存。

1<=T<=20,

1<=n<=10^6,1<=k<=34

1<=ai<=2^31

数据保证每个文件中所有n的和不超过10^7。


Output

对于每组数据,一行"Case #x: y"(不含引号)。x是一个整数,表示数据序号,从1开始编号。y可能是一个整数,表示任意排列后最小的分裂次数;也可能是一个字符串"Bad Alloc!!"(不含引号),表示无法满足所有请求。

Sample Input

2
10 20
432 4732 8747 9237 46372 294328 512565 5415 55724 32
2 1
1 1

Sample Output

Case #1: Bad Alloc!!
Case #2: 1

HINT

Buddy System 是一种神奇的内存管理算法。

Source

[Submit][Status]