曙光信息学奥林匹克第4次友谊赛试题第一试.doc

SGOI第四次竞赛试题第一试说明：1. 7月28日(星期六)上午8：00至12：00在中国曙光教育网-信息学奥赛专栏上公布第一试题目; 7月29日(星期日)上午8：00至12：00公布第二试题目，参赛者可下载题目，并作答。2. 本次竞赛采用黑闸子测试，参赛者必须严格按照试卷中要求的程序名、输入/出文件名及格式，进行作答。 3. 参赛者必须在当日16：00前将所有解答（.pas）及参赛者信息等文件用Winzip压缩。 4. 参赛者信息文件包括：参赛者所在省、市、学校、年级、真实姓名、指导教师、联系地址、指导教师的电子邮件。 5. 主办单位于7月28日下午18:00开始第一试测试、7月29日下午18:00始第二试测试，8月2日上午9：00在中国曙光教育网上公布参赛者成绩，随后将参赛者优秀的解答、测试数据、参考解答和解题报告，以学校为单位发给指导教师并在中国曙光教育网上公布。（注：若参赛者采用C语言或Qbasic语言参赛，请将对应程序的可执行文件（.exe）提交上来） 试题1.镇长的烦恼 （stops.pas ） 问题描述: Tom当上了镇长，春风得意。他的辖区内新开了一条高速公路，公路上有两个车站，坐标分别为A（xa，ya）、B（xb，yb），每天都有车辆从A站开往B站。公路附近有两个村庄（公路可能从村庄中穿过），村庄分布在如图所示的带状区域内，坐标为C（xc，yc），D（xd，yd），C、D两村每天都分别有m人要前往B站。 因为高速公路不可随意出入，所以需要在两车站之间的公路上合理地设置一些汽车停靠点，村民可步行至停靠点后进入高速公路，并免费乘车前往B站。每个村民每步行一千米（一个单位看作一千米）所得到的政府补贴为t元，政府维护一个停靠点所需花费为p元/年。于是，一个棘手的问题摆在了Tom面前：应如何设置这些停靠点，才能使政府的支出最小？ 给出一个年份year，请你帮Tom设计一个方案，使得镇政府从该年起的n年内总支出最小。 注意，村民只能进入停靠点而不能直接进入车站，但允许在车站处设置停靠点。 输入格式： 第一行四个数： xa ya xb yb 第二行四个数： xc yc xd yd 第三行四个数： m n t p （0=3000，0=10） 第四行： 年份 year （2000=year=30000） 以上数字，m，year，n为正整数，p，t为正实数，其余均为实数。 输出格式： 第一行 最小费用c（单位：元） 第二行 设置的停靠点数N（N为正整数） 以下N行，每行两个实数，代表停靠点的坐标 如有多解，任意输出一解即可。 所有实数保留四位小数。样例输入： 样例输出： 试题2.糊涂的记者 （SIGNPAS） 问题描述：在如今的信息社会中，时间-就是生命，对于记者们来说，如何以最快的速度传递消息就显得十分重要了，而为了尽快记录消息内容，速记也是必不可少的。速记就是用一些简单且特殊的符号表示一定的含义，具体如何对应依个人习惯而定，没有一种固定的表示方法。 Tom是一名报社的新闻记者，常常马不停蹄的跟着新闻跑，有时只能随手记下采访的内容，让人送回报社，而自己又奔赴下一个现场。不过Tom是一个糊涂的记者，有时忙中出错，把用自己的速记符号写的内容直接传回报社。因为一时联系不上Tom，但这条新闻又十分重要，要赶着在当天的报纸排版前整理出来，于是Tom的同事们只好来猜测Tom的速记符号的意思。幸运的是Tom的同事们与他共事的时间也不短了，对于Tom的一些用词情况有一定的了解，经过讨论，他们列出了一张可能性表来表示每一个速记符号可能与哪些单词相对应，并列出了对应的可能性有多大。 你的任务是：根据Tom的同事们提供的可能性表，找出一种可能性最大的速记符号与单词的对应方法（可能性应该相乘来计算）。 注意：每一个速记符号有且只有一个单词与其对应，每一个单词有不超过一个速记符号与其对应（可能没有速记符号与之对应）。 输入格式：文件的第一行有两个整数，分别为速记符号的个数n(1=n=100)和单词总m (1=m=500)。 从第1行到第n+1行为每个速记符号可能对应的单词及其可能性。 第i+1(1=i=n)行的第一个数Ci表示第i个速记符号可能与Ci个单词相对应，后面有Ci个数对(Nik，Rik)(1=k=Ci)，表示第i个速记符号与第Nik个单词相对应的可能性为Rik（Rik为大于0小于1的实数）。 输入样例： 输出格式： 输出文件仅包含一行，若有解则输出一个实数即最大的可能性，保留四位有效数字（四舍五入），若无解则输出NO ANSWER。 （当可能性大于1e-12时才被视为有解） 输出样例： 注意: 由于实数的精度误差，使用PASCAL的选手请采用Borland Pascal编译，使用C+的选手请采用djgpp编译。试题3. Binary Code (bincode.pas) 考虑一个N位的二进制串b1bN，其对应的二进制矩阵为： 然后将这个矩阵的行按照字典顺序排序，0在1之前。 你的任务是编写一个程序，给定排序后的矩阵的最后一列，求出已排序的矩阵的第一行。 例如：考虑二进制串（00110），排序后的矩阵为： 则该矩阵的最后一列为（1 0 0 1 0）。给出了这一列，你的程序应该确定第一行为（0 0 0 1 1）。 输入: 输入文件名为bincode.in。第一行包含一个整数N(0=20000)，表示