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

(GDOI'2001)

二试试题

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

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

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

4、程序完成膈，要按指定的提交文件名编辑成EXE文件，评卷时以EXE文件为准。

5、四个小时完成。

6、本次竞赛的最终解释权归GDOI委员会所有。

第一题  Dolores家的停车道(The Dolores' Driveway)

提交文件名：driveway.exe

问题描述：

    Dolores的家旁有一条停车道，整条停车道最多可以容纳26辆车，但是车道的宽度只能让一辆车通过。车道的进出口在两端，这样客人来访时停车会很方便。但是一旦有客人要离开，就会有麻烦：前面尚未离开的车必须先退出去，让那辆车离开，然后这些车以相反顺序退回来。由于有两个出口，所以如果现在有一辆车要离开，那么它离哪一端近，就从哪一端出去。如果该车处于正中央，则规定从左边离开。

    例如，现在停在停车道里的车从左到右依次是ABCDEFG。现在E车要离开，于是F和G必须从右边退出，让E车离开，然后以跟原来相反的顺序回到车道，于是车道里的车就成了ABCDGF。如果C车要离开，则A和B让路再退回，结果形成BADGF。现在D要离开，这时A和B给它让路，退回后车道中形成ABGF。

    请编写一个程序模拟这个过程。(每个数据都会有解)

输入格式：

    数据存放在当前目录下的文本文件“driveway.dat”中，一共n+2行。

    文件的第一行是一串大写英文字母，表示车辆在车道中停放在顺序。字母没有重复的，字母之间没有空格。第二行是一个数字n(n>=0)。接下来的 n 行中，每行只有一个大写英文字母，依次给出车辆离开的顺序。文件每一行开头和结尾都没有空格。

输出格式：

    答案输出到当前目录下的文本文件“driveway.out”中，一共n+1行。

    第一行输出最初车辆的顺序，接下来的 n 行输出每离开一辆车后剩余的车辆的排列顺序。文件每一行的开头和结尾都没有空格。

输入输出举例：

第二题  科学实验(Experiment)

提交文件名 exp.exe

问题描述：

    最近，我国科学家通过星球探测器分别从A星和B星上取得了n1，n2块结构相类似的陨石碎片，需要做n=min(n1,n2)次化学实验通过对比来研究它们，每次任取A、B星上各一颗碎片进行化学实验，由于实验中经过化学变化，碎片在实验后不可再用。另外，由于此种陨石碎片的特性受重量的影响很大，所以为了使实验效果达到最佳，科学家们希望能选出一种方案，使得每次实验的两颗陨石重量之差的绝对值的总和最小。

    现在，请你求出该最小总和为多少。

输入格式：

    输入文件为当前目录下的“exp.dat”。

    第一行为两个整数：n1  n2

    接下来的n1行，每行一个实数，表示A星上各颗陨石的重量。

    然后有n2行，每行一个实数，表示B星上各颗陨石的重量。

    注意：n1,n2<=500；每颗陨石碎片的重量不超过90。

输出格式：

    输出文件为当前目录下的“exp.out”。

    只有一个实数，表示所求得的最小总和。

第三题  被毁坏的玉米地(Crop Circles)

提交文件名：crop.exe

问题描述：

    “哈姆，外星人又在那了！”。埃塞和哈姆他们的玉米地是长方形的。每年在丰收之前，他们的玉米地都会很奇怪的遭到毁坏(据埃塞说是外星人干的)。所有破坏的地方都是以 1 米为半径的圆。哈姆发现，如果玉米地上建立一个适当的直角坐标系的话，那些圆心的坐标将都为整数。万幸的是，埃塞和哈姆有玉米保险，但必须把损坏的面积统计出来。

输入格式：

    输入文件为当前目录下的文本文件“crop.dat”中。

    文件的第一行为一个整数n(0<n<=200)，表示圆圈的个数。以下 n 行每行有两个整数 x 和 y ，由空格分开，代表圆心坐标。数据中不存在两个完全重合的圆。

输出格式：

    输出文件为当前目录下的“crop.out”。

    输出统计出的总面积，四舍五入到小数点后4位。(π=3.1415926535)

输入输出样例：

第四题  自动计算机器(NTA)

提交文件名：nta.exe

问题描述：

    一个自动计算机器(NTA)是由一些平行的处理器组成。处理器拥有有限种状态，被放在一个无限的三角形格架上。在三角形格架的顶端，只有一个处理器。下一行有两个，以后每一行都比上一行多一个。每一个处理器都于下一行的两个子处理器建立着联系。NTA的计算工作是自下而上的。每一个处理器的状态是由他下一行的两个子处理器的状态和一个状态转换表所决定。输入给NTA的一行处理器的状态。由 n 个字母表示位于同一行的 n 个处理器的最初状态。由每两个子处理器的状态和状态转换表来计算上一行每个处理器的状态。直到求出位于顶端的那个处理器的状态为止。但，在计算过程中，状态可能不是唯一确定的。

    一些状态被认为是合法的。经过计算，顶端的处理器的状态可以为合法状态的输入为合法输入。如果顶端处理器的状态不可能为合法状态，那么，输入被认为非法的。下边是一个拥有三个状态NTA的例子，用“a”、“b”、“c”来代表三个状态，“c”被认为是唯一合法的状态。

    下边的表格是由“bba”的两个计算过程。左边的得到了非法状态“a”；但是，右边的得到了合法的状态“c”。一个输入，经过计算只要能得到合法的状态，就认为是合法的输入。但是“bbb”被认为是非法输入。因为，它唯一的计算结果“a”为非法的。

输入格式：

    数据存放在当前目录下的文本文件“nta.dat ”中；文件中包含 t 组数据。

    要求用小写字母代表处理器的状态。因此，如果NTA有五个状态的话，表示成“a”、“b”、“c”、“d”和“e”。合法的状态位于后面，所以如果要两个合法状态的话，应是“d”和“e”。

    文件的第一行为一整数 t ，随后跟着 t 组数据。

    每一组数据的第一行为两个整数 n 和 m ，表示NTA的状态的个数和合法状态个数。以下n×n行为NTA的状态转换表。第(i-1)×n+j=1行表示左子处理器为第 i 个状态，右子处理器为第 j 个状态时所能确定的状态。如果有多个状态，则挨着给出。第n1×n1+2行为所输入的状态。行结束为一个“#”。

    NTA最多有15个状态，输入的最初状态最多为15个字母。

输出格式：

    答案输出到当前目录中的文本文件“nta.out”中。共有 t 行，第 i 行为第 i 个数据的输出结果。

    如果为合法输入，则输出“accept”，否则输出“reject”。

输入输出样例：