2008年青岛市程序设计竞赛试题(高中组) 4页

2008年青岛市程序设计竞赛试题（高中组）说明：1.必须以题目中规定的文件名进行保存，并用FTP上传到指定文件夹中。FTP上传使用说明在试题最后。请选手每做完一道题及时上传一次，以确保因机器故障引起的文件丢失。2.比赛时间为：90分钟，每道试题100分。3.使用竞赛规定的文件格式输入，输出全部时间限制为1s，内存限制为64m。1.机房的字典(lexicon.pas/lexicon.in/lexicon.out)描述：很少有人知道tHeem_Lody所在的机房有一部含有W(1<=W<=600)个单词的字典，每个单词包含之多25个小写字母。由于机房噪音很大(包括主机风扇的嗡嗡声，空调吹气的呼呼声，还有楼下买菜老大妈的吆喝声……)，导致机房成员们有时候听到的单词不具有任何意义。比如，tHeem_Lody有一次听到一句话是“orzsalsnod”，其实这句话原本的意思是“orzalno”，那另外的两个s和一个d是噪音造成的。tHeem_Lody希望你能帮助他破译一些长度为L(2<=L<=300)的有一些被杂音扰乱的句子（只是包含小写字母a..z），并且可以保证其中只是加入了一些另外的字母。tHeem_Lody希望你能去除的字母最少使得这个句子能有意义（即仅由一些能够在字典上找到的词构成）。输入格式：第一行：两个整数W和L，用一个空格隔开第二行：L个小写字母，表示收到的句子第3..W+2行，机房的字典，每行一个单词输出格式：一个整数，将句子变得有意义所需要去掉的最少字母个数样例输入：\n610orzsalsnodorzmilkwhitealnoblackfarmer样例输出：32.机房的饮水机(fountain.pas/fountain.in/fountain.out)描述：夏天到了，机房的饮水成了一个不容忽视的问题。tHeem_Lody在攒了很久钱以后，决定为机房买一台饮水机，他希望把饮水机安放到何时的位置。tHeem_Lody知道机房有N(1<=N<=10000)个成员，第i个成员的位置都可以用一对整数坐标（xi,yi）来表示(-10000<=xi<=10000;-10000<=yi<=10000)饮水机必须放置在一个用整数坐标可以表示的点上，但不能放在机房成员的电脑桌上(即不能和人和一个机房成员的坐标重合)，因为这样会遮盖某人显示器使得其可以避开老师的巡查肆无忌惮的玩游戏。夏天所有机房的OIers的需水量都是很大的，tHeem_Lody希望饮水机与所有OIers的距离和最小，方便所有人接水。为了简化问题，这里的距离指的是曼哈顿距离，即|X-Xi|+|Y-Yi|，其中X，Y和Xi和Yi分别是饮水机的坐标和机房成员的坐标。另外，由于挨得太紧会很热，没有两个机房成员的坐标是相邻的。即一个成员上下左右四个点内不会有另外的成员。你能帮助tHeem_Lody找到一个位置放置饮水机，使得饮水机到所有机房成员的曼哈顿距离之和最小吗？（可能有多个位置都能达到最小值）。\n输入格式：第一行：一个单独整数N第2..N+1行：第i+1行包括两个整数（xi,yi），用一个空格隔开，表示第i个机房成员的位置输出格式：第一行：一个整数，表示饮水机到所有机房成员曼哈顿距离的最小和。样例输入：41-301-211-1样例输出：10样例说明：最小距离是10，tHeem_Lody有四个点可以放置饮水机：（0，-1），（0，0），（1，0）和（1，1）。3.机房的值日(duty.pas/duty.in/duty.out)描述：\n机房几乎每周都要照例做一次值日以保持卫生，tHeem_Lody知道一共有N(0