广东省青少年信息学奥林匹克竞赛决

1 / 13 广东省青少年信息学奥林匹克竞赛决 1.严格按照题目所要求的格式进行输入、输出，否则严重影晌得分。 2.题目测试数据有严格的时间限制，超时不得分。 3.输入文件格式不用判错 ;输入输出文件名均已给定，不用键盘输入。 4.程序完成后，要按指定的提交文件名编译成 EXE 文件，评卷时以 EXE 文件为准。 5.三个半小时完成。 6.本次竞赛的最终解释权归 GDol评委会所有。 试题名称 替换程序 特修斯与米诺牛 旅游 星际旅行 提交文件名 输入文件名 2 / 13 输出文件名 满分 30 40 40 40 第一题替换程序麻烦 !(Trouble 提交文件名 :Trouble-exe 问题描述 : Toxicco 化学公司开发了一种新的，但有点不稳定的，在热酸炉中电镀 金属的工艺流程。这流程需要不断监测炉内的温度和电压。太低的温度或者太高的电压会导致已经融化的金属凝结成一团堆积在炉底，损坏设备 :另一方面，如果温度升得太高，酸雾会释放到大气中，污染环境 :如果电压3 / 13 太低了，会导致爆炸。 一个人工智能的流程控制系统，不但可以保持炉内的温度和电压处于安全的范围内，还可以不断调整这两者，使得电镀流程达到最快的速度。 不幸的是，软件开发者告诉 Texicc0 公司控制系统里还存在一些小错误，他们最快也要 9 个月后才能修复完。Texicco 公司里有一些员工表示不满，怀疑软件 开发者是否会按时完成任务。但是， Toxicco 公司希望尽早动工。他们请你帮忙编写一个相对简单的程序，以在这段过渡时期内运作。 编写一个程序，读入温度和电压可以的波动范围，以及当前温度、电压，判断该状态 是否安全。一个安全的状态由以下四条线决定。 两个下界 aT+bV=c，其中 T 表示温度， V 表示电压。 a， b， c 是输入数据给出的常量。 两个上界 aT+bV=c 其中 T， V， A， b， c 定义如上 在以 t， v 建立的直角坐标系中，这四条线形成一个方形区域。 输入数据保证该方形区域是封闭的。 输入格式 : 数据存放在当前目录下的文本文件 trouble-dat中，文件共有 5 行。 第一行有三个数 abc表示第一个下界 : 4 / 13 第二行有三个数 a， b， c 表示第二个下界 ; 第三行有三个数 a， b， c 表示第一个上界 : 第四行有三个数民 b， c 表示第二个上界 : 第五行有两个数 tV表示当前的温度和电压。 数据以浮点数形式给出，每两个数之间有一个或者多个空格，每一行数的长度不超过 40。 输出格式 : 数据输出到当前目录下 中，只有一行。如果在安全范围内，输出 SAFE，否则输出 UNSAFE。注意输出只有一行，行首行尾不要有多余空格。 输入输出举例 : 样例一 UNSAFE - 样例二 5 / 13 SAFE - 第二题特修斯与米诺牛 Theseusandtheminotaur 提交文件名 : 问题描述 z 古希腊关于特修斯与米诺牛 (一只人身牛头的怪兽的传说家喻户晓。故事中有一个庞大的地下迷宫，特修斯就是在迷宫中与米诺牛搏斗，并最终杀死了米诺牛，获得自由。现在让我们来重现这段故事。 迷宫有很多的石洞 (石洞都是圆形的 )，它们之间有通道相通。特修斯与米诺牛都有自己的行动规则。特修斯进入迷宫时带着蜡烛和一些能发出磷光的涂料，他准备用涂料来做标记自己走过的路口。他的计划如下 :先沿着一条通道往前走，到达一个石洞后向右转，然后贴着墙走 (他 是一个左撇子，左手持剑 )。他在黑暗中摸索前进，直到他来到一个出6 / 13 口。如果这个出口未做过标记，他就会做上标记然后钻进去。如果是己经标记过的，那么他就不予理睬，继续前进。如果发现自己与米诺牛在同一个洞里，他就会点燃蜡烛 (因为米诺牛见强光就会失明 )把它杀死。如果他在通道里遇到米诺牛，那么他就会被它杀掉，因为通道太窄，他无法点蜡烛，也没有给他自由搏斗的空间。当他进入一个石洞后发现米诺牛己经来过，那么他就会点一根蜡烛放在洞里，然后直接从米诺牛离开的那个洞口钻进去，而不管该洞口是否标记过。 与此同时，米诺牛也在 寻找特修斯。虽然它身体庞大，行动迟缓，但是它很了解迷宫的结构，所以它的移动速度与特修斯一样快。当特修特从一条通道出来进入某个石洞它也同时进入某个石洞。每次进入石洞之后，它先向左转，然后沿顺时针方向前进，它找到一个自己没有做过标记的洞口，就做上标记，然后进入其中。在通道里候，如果它发现它将要进入的那个石洞里有蜡烛火光，那么它会转回到刚才的洞里。 例如，一个迷宫结如下 : 假定特修斯从 Ac 之间通道出发，向 c 前进，而米牛从FH之间通道出发，向 H 前进。进入 c 之后，特修斯进入 D，此时，米 诺牛也进入 G。然后，特修斯从 D 往 G，米诺牛从 G往 D，这样，米诺牛会在通道里把特修斯杀死。 7 / 13 假如特修斯仍然从 Ac 之间通道出发向 c 前进，而米诺牛从 DG之间通道出发，向 G 前进。然后特修斯依次进入 c、D、 G，米诺牛依次进入 G、 E、 F。特修斯进入 G 后，他发现米诺牛己经到过这里，于是他点了一根蜡烛放在洞里，然后直接从通往 E 的出口出去，而不是去 H。特修斯到达 E，米诺牛刚好到达 H。米诺牛在从 H 到 G 时，发现了 G 中的火光，于是返回 H，这时特修斯已经追到 F。然后米诺牛尝试进入 E，但仍然折回到 H。这样，特修斯刚好赶到 H，并把米牛杀死。 输入格式： 迷宫 n(3=n=26)个石洞。文件一共有 n+1行，前 n 行中，每行第一个大写字母表示某一个石洞，紧接着是一个分号，其后是一串大写字母，表示与其连接石洞 (以逆时钟顺序给出 )。每个石洞都至少与一个石洞相连，而且一定不会与自己相连。第 n+1 行以 开头，接着两对字母，第一对表示特修斯出发通道，第二对表示米诺牛出发通道。每一对字母都表示从第一个石洞前往第二个石洞。一开始修斯和米不会在同一个通道里。每一行开头和结尾都没有空格，字符之间也没有空格。 输出格式： 输出三种情况 : 1、特修斯被米诺牛杀死，输出两行 : 2、石洞 1 石洞 2 8 / 13 表示特修斯在从石洞 1 通往石洞 2 的通道里被杀死。 2、特修斯把米诺牛杀死，输出两行 : 1、石洞 表示特修斯在该石洞里把米诺牛杀死。 3、谁也杀不了谁，输出一行 : 0 输入输出举例 : 样例一 A:Bck 2 DG D:BAcG F:HE G:HED B:AD E:FGH H:FEG c:AD AcFH 9 / 13 样例二 A:Bck 1 H D:BAcG F:HE G:HED B:AD E:FGH H:FEG c:AD AcDG 第三题旅行 Travel 提交文件名 :tEWeLeyte 问题描述 : GDoI队员们到 Z 镇游玩。 Z 镇是一个很特别的城镇，它有 m+1条东西方向和 n+1条南北方向的道路，划分成 m*n个区域。 Z 镇的名胜位于这些区域内。从上往下数第 i 行，从左往右数第 j 列的区域记为 D(i， j)。 GDoI队员们预先对这10 / 13 m*n 个区域打分 V(i， j)(分数可正可负 )。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便集合，队员们只能在某一范围内活动。我们可以用 (m1， nl)与 (m2，n2)(m1=m2， n1=n2)表示这样的一个范围 :它是这些区 域 的 集 合 :D(i ， j)|m1=I=m2 ，n1=j=n2。 GDoI队员们希望他们活动范围内的区域的分值总和最大。 当然，有可能队员们一个地方也不去 (例如，所有区域的分值都是负数。当然，如果某范串内的分值总和为零的话，他们也会去玩 )。也有可能他们游览整个 Z 镇。你的任务是编写一个程序，求出他们的活动范围 (m1， nl)， (m2， n2。 输入格式 : 输入数据存放在当前目录下的文本文件 中。数据有m+1 行。第一行有两个数 m， n(m， n 定义如上 )。其中，（ 1=m=250， 1=n=250）。接下来的 m 行，每行 n 个整数，第 i 行第 j 个数表示分值 V(i，j)(-128=V(i， j)=l27)。每两个数之间有一个空格。 输出格式 : 答案输出到当前目录下的 中，只有一行，分两种情况 : 1队员们在范围（ m1， n1）， (m2， n2)内活动，输出该范围内的分值。 2.队员们不想去任何地方，只需输出 No。 11 / 13 注意 :不要有多余空行，行首行尾不要有多余空格。 输入输出举例 : 样例一 样例二 45 146 23 No 1 23 45 -1 2 1 678910 -4 3-6 -11121314-15 1617181920 第四题星际旅行 (SpaceTravel) 提交文件名 问题描述 12 / 13 飞船准备从地球出发，访问一系列的星球，假设访问顺序固定。飞船从一个星球到另一个可以借助普通空间或 超空间中的一种空间飞行。超空间使得飞行距离缩短，但能源消耗将大大增加，若飞船在超空间中总共飞行 d 光年，则能源消耗为 d 单位 !而飞船在普通空间总共飞行 d 光年，能源消耗正好是 d 单位。 请你编程求出访问这些星球所需的最少能源。 输入格式 : 输入文件为当前目录的 ; 第一行一个整数 N(1=N=50)，表示访问的星球数。 接下来 N行中的第 j行有两个整数 h