《曙光信息学奥林匹克第3次友谊赛试题.doc》由会员分享，可在线阅读，更多相关《曙光信息学奥林匹克第3次友谊赛试题.doc（5页珍藏版）》请在金锄头文库上搜索。
1、SGOI第三次竞赛试题要求：初中组SG1、SG2、SG5必做,高中组全做每题存盘文件名分别为：sg1.pas,sg2.pas,sg3.pas,sg4.pas,sg5.pas所有题目的输入文件为sgin.txt输出文件为sgou.txt SG1电话局选址 在一个山区乡镇里，分布着若干个村庄(n10)。这个镇计划筹建一个电话模块网，在这一模块网中每个村庄被连接到一起，村庄与村庄之间只用一条电缆连接，并且除了首尾的两个村庄只分别连接着一个村庄外，其他的任一个村庄恰连接着两个村庄。图1给出了各个村庄的分布情况，图中已标出了各个村庄的坐标，连接各村庄的直线距离单位为千米。 你的任务是选择一个村庄作为电话
2、模块网的起点，希望埋设的电缆线长度尽可能的短。1.输入输入文件由若干行数据序列组成，第一行，一个数据表示村庄的个数；第二行开始，每行两个数据，数据之间用一个或若干个空格隔开，用以表示每个村庄的坐标。镇中心的坐标即为坐标中心。2.输出输出结果的第一行为该电话模块网中起点村庄的坐标；以下第i行数据是第i个是村庄的坐标，最后一行是一个数据，即：耗用电缆长度的最小值。3.输入、输出样例： SG2 海上搜索 在南海的某一海面内岛屿和海洋交错衡生,进行海上搜索作业，先对搜索区域的海洋图分割成若干个MN大小相同的网格,其中M（M50）表示行,N(N50)表示列,在网格中以1表示海洋,0表示岛屿（位于纵向或横
3、向相邻的成片数字视为一个岛屿）如图1有3个岛屿，图2有1 个岛屿。你的任务是为这次的海上搜索作业确定一个基准区域，所谓的基准区域是指如上图的图像中的一块矩形区域：（1）每一个岛屿都有部分面积（网格）在此区域内；（2）在满足（1）的条件下，区域面积最小。一幅图像中的基准区域可能不是唯一的，但各基准区域面积必定是相同的。根据给定的图像，确定其基准区域的面积。输入数据：输入文件的第一行有两个整数M和N，中间用一个空格分隔。随后有M行，每行有N个数字（0和1），数字间用一个空格分隔，构成MN的网格。输出数据：输出文件的第一行为基准区域的面积，即基准区域的网格数。输入输出样例： SG3 获取学分 学校实
4、行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如Frontpage必须在选修了Windows操作基础之后才能选修。我们称Windows操作基础是Frontpage的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，。 例如:表中1是2的先修课，2是3、4的先修课。如果要选3，那么1和2都
5、一定已被选修过。 你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。输入数据：输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1N300,1MN。以下N行每行代表一门课。课号依次为1，2，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。输出数据：输出文件每行只有一个数。第一行是实际所选课程的学分总数。以下各行的数，表示所选课程的课号。输入输出样例： SG4 求交集多边形面积 在平面上有两给定的凸多边形，若两凸多边形相交
6、，则它们的交集也是一个凸多边形。若两凸多边形不相交，指的是两凸多边形相离或仅限于边界点与边上相交，则相交面积为0。如图所示： 你的任务是编程给出交集多边形的面积。两给定的凸多边形按顺时针方向依次给出多边形每个顶点的坐标。输入数据：输入文件第一行为一整数M，表示第一个凸多边形的边数，以后M行分别给出了M个顶点的坐标；接着，给出第二个凸多边形的边数N，以后N行分别给出了N个顶点的坐标。输出数据：只一个数据即交集面积，保留两位小数点。输入输出样例：SG5 组数问题 一集合有M个（M50）数，把其中末位数或首位数相等的两个数相加，组成一个新的数使其和最大(如：9 99 999三个数，则应选择后面两个相
7、加)。你的任务是找出符合条件的新数，并统计输出该集合至多有的N个新数。每一个输入的数位长m100，输出的数位长不限，要完整地输出。例如：M=7130892087390935763987637275999309876562843674932745675951000000101010101010101010101010100000 则可以组成： 1000000101010101010101010101010113089 首位为130987656284367494262204870 末位为5 等共有5个新数。输入数据：输入文件的第一行为输入数的个数，以下各行为各输入数。输出数据：输出文件的第一行为至多能组成新数的个数，以下各行为组成的新数。输入输出样例： Sgin.txt713089208739093576398763727599930987656284367493274567595 1000000101010101010101010101010100000Sgin.txt510000001010101010101010101010101130892088699830987656284367493274603358987637276274 30987656284367494262204870
