置）这样岛上的居民就能用手机通话了，所有的基站的覆盖距离都是d，在距离d范围内的小岛都能收到基站发送的信号。
我们用笛卡尔坐标系来表示这个问题，定义x轴为海滩，x轴上方是大海，下方是陆地。现给出每个小岛的位置（用x-y坐标表示）和基站的覆盖范围d，你的任务就是写一个程序，计算出可以覆盖所有的小岛，至少需要在海滩上安装多少基站？
Input
输入包含多组数据。对每组数据，第一行包含两个整数n（1 <= n <= 1000）和d，n代表小岛数量，d代表基站的覆盖距离。接下来有n行，每行包含两个整数，表示小岛的位置坐标。输入n=0,d=0时退出。 Output
对每组数据，输出包含数据组数，格式如sample，后跟最少需要安装的基站数，如果无解，输出-1。 Sample Input 3 2 1 2 -3 1 2 1 1 2 0 2 1 -2 0 2 0 0
Sample Output Case 1: 2 Case 2: 1 Case 3: -1
和MM去上课
Time limit: 1000MS Memory limit: 32768K
Total Submit: 31 Accepted: 12
北大的很多研究生住在万柳校区，他们每天要坐公交或骑车去4.5公里远的燕园上课。由于北京的交通很烂（我想也是很烂）,许多同学选择骑车去上课。 查理同学和其他同学的骑车习惯不同，其他同学都是以固定的速度骑行，查理则是跟某个MM一起，这样就不会觉得无聊。当查理出发的时候，他会寻找一个MM作伴去燕园。如果找到了PLMM，他就会和她一起，否则就继续物色。在去燕园的路上，如果有某个MM速度比较快，超过他了，他就会丢下身边的MM去追那个更快的MM，然后和她一起去燕园。 我们假设查理出发的时刻为0，现给出很多MM的出发时间和速度，你来计算一下查理什么时候能到燕园呢？
Input
包含多组数据。每组数据第一行以个整数N(1<=N<=10000)，代表MM数，N=0时退出，接下来有N行，每行代表一个MM的骑行信息。格式：Vi Ti。0 < Vi <= 40，代表骑车速度(km/h)，Ti是该MM的出发时间（s），Ti可能小于0。
Output
每行输出代表一组数据。输出查理到达燕园的时间，不满1秒的按1秒算。
Sample Input
4 20 0 25 -155 27 190 30 240 2 21 0 22 34 0
Sample Output
780 771
2011-软件091-092-实验十
Huffman Coding
Time limit: 1000MS Memory limit: 32768K
Total Submit: 58 Accepted: 55
给定一个数字N，代表有N种不同的字符，已知每种字符的出现次数，现在要求你设计一种编码，使得任意一个编码都不是另外一个编码的前缀，并且使得这些字符经过编码压缩之后的总长度最小；
输入
一个数字N 代表有多少种不同的字符(0<=N<=1000) N个数字 每个数字代表一种字符的出现次数 输出
一个数字，代表总的编码长度
Sample Input 5 1 2 3 4 5 3 3 8 8
Sample Output 33 30
HINT: 比如第2组数据 A字符出现3次，B字符出现8次，C字符出现8次 则A编码可以为00 B为01 C为1 总长度为 3*2 + 8*2 + 8*1 =30
2011-软件091-092-实验十一
部分背包问题
Time limit: 3000MS Memory limit: 32768K
Total Submit: 76 Accepted: 58
一个商人带着一个能装M千克的背包去乡下收购货物，准备将这些货物卖到城里获利。现有N种货源，且知第i种货物有Wi千克，可获利Pi元。请你设计一个程序以帮助这个商人收购货物，使得他能获利最高。 Input
第一行输入一个整数 T(1 <= T<= 64), 表示测试数据数量。
每组CASE三行，第一行包含两个整数N(1 <= N <= 1024),M(1 <= M <= 4096)，表示资源的数量以及背包的容量。
第二行包含N个整数Wi(1 <= Wi <= 4096) 表示第i种货物有Wi千克。 第三行包含N个整数Pi(1 <= Pi <= 10086) 表示第i种货物可获利Pi元。 Output
对于每组Case， 输出一行:\表示当前是第几组CASE， Y表示最大获利。 Sample Input 2 3 5 1 2 3 3 2 1 7 4
1 2 3 2 1 1 4 1 2 10 3 2 1 100 Sample Output Case #1: 5 Case #2: 100
Source:
2011-软件091-092-实验十二
最小生成树
Time limit: 1000MS Memory limit: 32768K
Total Submit: 66 Accepted: 62
在一张图上有N个点，点与点之间的连接的花费都已经告诉你了，请你设计一下，如果解决这个“最小生成树”的问题。
输入
首先输入一个数字N（0〈=N〈=100）
然后输入一个N*N的矩阵 其中第i行第j列的数字k表示从点i到点j需要的花费。
输出
一个数字，最少需要多少花费才能使得整张图任意两点都直接或者间接连通（也就是最小生成树的权） Sample Input 5
0 41 67 34 0 41 0 69 24 78 67 69 0 58 62 34 24 58 0 64 0 78 62 64 0 0 2 0 1 1 0
Sample Output 116 0 1
2011-软件091-092-实验十三
最小生成树
Time limit: 1000MS Memory limit: 32768K
Total Submit: 76 Accepted: 60