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