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

1.严格按照题目所要求的格式进行输入、输出，否则严重影晌得分。

2.题目测试数据有严格的时间限制，超时不得分。

3.输入文件格式不用判错;输入输出文件名均已给定，不用键盘输入。

4.程序完成后，要按指定的提交文件名编译成exe文件，评卷时以exe文件为准。

5.三个半小时完成。

6.本次竞赛的最终解释权归gdol评委会所有。

试题名称

替换程序

特修斯与米诺牛

旅游

星际旅行

提交文件名

trouble.exei

theseus.exe

travel.exe

space.exe

输入文件名

travel.dat

theseus.dat

travel.dat

space.dat

输出文件名

travel.out

theseus.out

travel.out

space.out

满分

30

40

40

40

第一题  替换程序 麻烦!(trouble〉

提交文件名:trouble-exe

问题描述:

toxicco化学公司开发了一种新的，但有点不稳定的，在热酸炉中电镀金属的工艺流程。这流程需要不断监测炉内的温度和电压。太低的温度或者太高的电压会导致已经融化的金属凝结成一团堆积在炉底，损坏设备:另一方面，如果温度升得太高，酸雾会释放到大气中，污染环境:如果电压太低了，会导致爆炸。

一个人工智能的流程控制系统，不但可以保持炉内的温度和电压处于安全的范围内，还可以不断调整这两者，使得电镀流程达到最快的速度。

不幸的是，软件开发者告诉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行。

第一行有三个数a b c表示第一个下界:

第二行有三个数a，b，c表示第二个下界;

第三行有三个数a，b，c表示第一个上界:

第四行有三个数民b，c表示第二个上界:

第五行有两个数tv表示当前的温度和电压。

数据以浮点数形式给出，每两个数之间有一个或者多个空格，每一行数的长度不超过40。

输出格式:

数据输出到当前目录下"trouble.out"中，只有一行。如果在安全范围内，输出"safe"，否则输出"unsafe"。注意输出只有一行，行首行尾不要有多余空格。

输入输出举例:

样例一

trouble.dat

trouble.out

35.0 -5.0 375.o

unsafe

0.0 1.0 65.0

-10.0 32.5 3000.0

55.0 -30.0 1350.0

15.0 75.2

样例二

trouble.dat

trouble.out

35.0 –5.0 375.0

safe

0.0 1.0 65.o

-10.0 32.5 3000.o

55.0 -30.0 1350.o

25.0 70.6

第二题特修斯与米诺牛〈theseus and the minotaur〉

提交文件名:theseus.exe

问题描述z

古希腊关于特修斯与米诺牛(一只人身牛头的怪兽〉的传说家喻户晓。故事中有一个庞大的地下迷宫，特修斯就是在迷宫中与米诺牛搏斗，并最终杀死了米诺牛，获得自由。现在让我们来重现这段故事。

迷宫有很多的石洞(石洞都是圆形的)，它们之间有通道相通。特修斯与米诺牛都有自己的行动规则。特修斯进入迷宫时带着蜡烛和一些能发出磷光的涂料，他准备用涂料来做标记自己走过的路口。他的计划如下:先沿着一条通道往前走，到达一个石洞后向右转，然后贴着墙走(他是一个左撇子，左手持剑)。他在黑暗中摸索前进，直到他来到一个出口。如果这个出口未做过标记，他就会做上标记然后钻进去。如果是己经标记过的，那么他就不予理睬，继续前进。如果发现自己与米诺牛在同一个洞里，他就会点燃蜡烛(因为米诺牛见强光就会失明)把它杀死。如果他在通道里遇到米诺牛，那么他就会被它杀掉，因为通道太窄，他无法点蜡烛，也没有给他自由搏斗的空间。当他进入一个石洞后发现米诺牛己经来过，那么他就会点一根蜡烛放在洞里，然后直接从米诺牛离开的那个洞口钻进去，而不管该洞口是否标记过。

与此同时，米诺牛也在寻找特修斯。虽然它身体庞大，行动迟缓，但是它很了解迷宫的结构，所以它的移动速度与特修斯一样快。当特修特从一条通道出来进入某个石洞它也同时进入某个石洞。每次进入石洞之后，它先向左转，然后沿顺时针方向前进，它找到一个自己没有做过标记的洞口，就做上标记，然后进入其中。在通道里候，如果它发现它将要进入的那个石洞里有蜡烛火光，那么它会转回到刚才的洞里。

例如，一个迷宫结如下:

假定特修斯从ac之间通道出发，向c前进，而米牛从fh之间通道出发，向h前进。进入c之后，特修斯进入d，此时，米诺牛也进入g。然后，特修斯从d往g，米诺牛从g往d，这样，米诺牛会在通道里把特修斯杀死。

假如特修斯仍然从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

表示特修斯在从石洞1通往石洞2的通道里被杀死。

2、特修斯把米诺牛杀死，输出两行:

1、石洞

表示特修斯在该石洞里把米诺牛杀死。

3、谁也杀不了谁，输出一行:

0

输入输出举例:

样例一

theseus.dat

theseus.out

a:bck

2

d g

d:bacg

f:he

g:hed

b:ad

e:fgh

h:feg

c:ad

@acfh

样例二

theseus.dat

theseus.out

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队员们预先对这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〉。

输入格式:

输入数据存放在当前目录下的文本文件"travel.dat"中。数据有m+1行。第一行有两个数m，n(m，n定义如上)。其中，（1<=m<=250，1<=n<=250）。接下来的m行，每行n个整数，第i行第j个数表示分值v(i，j)(-128<=v(i，j)<=l27)。每两个数之间有一个空格。

输出格式:

答案输出到当前目录下的"travel.out"中，只有一行，分两种情况:

1．队员们在范围（m1，n1），(m2，n2)内活动，输出该范围内的分值。

2.队员们不想去任何地方，只需输出"no"。

注意:不要有多余空行，行首行尾不要有多余空格。

输入输出举例:

样例一

样例二

travel.dat

travel.out

travel.dat

travel.out

4 5

146

2 3

no

1 –2 3 –4 5

-1 –2 –1

6 7 8 9 10

-4 –3 -6

-11 12 13 14 -15

16 17 18 19 20