Algorithm 版 (精华区)

发信人: sino (茶水先生), 信区: Algorithm
标  题: 中山大学计算机竞赛（ZSUCPC 2001）第2试试题
发信站: 哈工大紫丁香 (2001年08月27日10:16:16 星期一), 站内信件

发信人: Northming (必有谋猷裨帝右), 信区: ACMICPC
标  题: 第四届第二试第一题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:15:37 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第四届第二试第一题
发信站: 逸仙时空 Yat-sen Channel (Sun May 13 09:52:54 2001), 站内信件


第一题 超级分子（40分）

可执行文件：molecule.exe
输入方式：键盘输入
输出方式：屏幕输出

这个问题是在与人造燃料研制相关的分子工程学当中抽象出来的：用四个等长的分
子链合成一个超级分子。在这里我们使用一种简化的二维模型：超级分子是由四条
两两平行、相互扣在一起的分子链形成的。"扣在一起"，即两条分子链共享一个分
子。
举例来说，假设我们有四个长度都是12的分子链：
         OIMDIHEIAFNL
         CHJDBJMHPJKD
         LCBJOJGIEKBO
         KAINLHLOLBBJ

它们可以合成下面的超级分子：

   O     L                                   O  C
   I     C                                   I  H
   M     B                                   M  J
CHJDBJMHPJKD                                 D  D
   I     O            - 或 -          LCBJOJGIEKBO
   H     J                                   H  J
   E     G                                   E  M
   I     I                                 KAINLHLOLBEJ
   A     E                                   A  P
   F     K                                   F  J
KAINLHLOLBEJ                                 N  K
   L     O                                   L  D

在这个问题里，我们对超级分子的结构有若干限制：
1． 四条分子链中任何一条都可以放在超级分子的水平或垂直"槽"中，如上图所示。
2? 如果一条分子链放在超级分子的两条水平槽之一，它必须保持原本从左到右的
顺序，也就是说，它不可以反转。
3   如果一条分子链放在超级分子的两条垂直槽之一，它从上到下的顺序必须和原
本从左到右的顺序相同，换句话说，它也不可以反转。
4． 超级分子中心围起来的矩形区域的面积必须尽可能大，而且不能是零。面积尽
量大的限制是从燃料挥发性的准则而得来的。面积有非零的限制，是因为不论水平
还是垂直分子链彼此接触都会引起某种副作用。
5． 所有分子链两端都应当延伸出超级分子中心的矩形区域至少一个分子的长度。
换言之，没有分子链的第一个或最后一个分子能成为超级分子中心的矩形边界的一
部分。

输入
输入有四行，每行12个字符，分别代表四个长度为12的分子链。每种分子用一个大
写字母表示。由于分子数目的限制，我们将只使用A到P这16个大写字母。分子链的
第一个分子就是每行的第一个字符。

输出
请将四条分子链合成的超级分子中心的矩形区域的面积按以下样例的格式输出。这
个数字应当是给定的四条分子链所能合成的所有超级分子中心的矩形区域面积的最
大值。
如果给定的四条分子链无法合成超级分子，请输出0。

输入样例            输出样例
CDBADCBBEFEF
DACCBADAFEAB
EFBDCAADBDCD
ABCDABCDABCD        48

ABABABABABAB
CDCDCDCDCDCD
EEEEEEEEEEEE
FFFFFFFFFFFF        0


--
※ 修改:．mk 于 May 13 09:54:33 修改本文．[FROM: 211.66.134.4]
发信人: Northming (必有谋猷裨帝右), 信区: ACMICPC
标  题: 第四届第二试第二题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:15:42 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第四届第二试第二题
发信站: 逸仙时空 Yat-sen Channel (Sun May 13 09:58:06 2001), 站内信件

第二题 大众批萨？（40分）
可执行文件：pizza.exe
输入文件：pizza.in
输出文件：pizza.out

你准备为你和朋友们订一个批萨，他们告诉你每个人希望批萨里有和没有什么材料
。当然，他们也明白到只有一个批萨，所以没有人期望他所有的要求都得到满足。
你能订一个批萨满足他们每个人至少一项要求吗？
你订批萨的那间店子提供如下的批萨口味，你可以在一个批萨中要或不要当中任何
一项：

代码    口味
A       凤尾鱼（Anchovies）
B       黑橄榄（Black Olives）
C       加拿大熏肉（Canadian Bacon）
D       方丁大蒜（Diced Garlic）
E       浓奶酪（Extra Cheese）
F       鲜花椰菜（Fresh Broccoli）
G       青胡椒（Green Peppers）
H       火腿（Ham）
I       意大利香肠（Italian Sausage）
J       加拉佩诺胡椒（Jalapeno Peppers）
K       波兰熏肠（Kielbasa）
L       瘦牛肉（Lean Ground Beef）
M       蘑菇（Mushrooms）
N       脱脂羊乳酪（Nonfat Feta Cheese）
O       洋葱（Onions）
P       胡椒（Pepperoni）

你的朋友每人给你一行文字描述他们的批萨口味。例如，
+O-H+P;
意味着某位朋友将接受一个含洋葱，或不含火腿，或带有胡椒的批萨。而
-E-I-D+A+J;
表示某位朋友将接受一个不含浓奶酪或意大利香肠或方丁大蒜的，或带有凤尾鱼或
加拉佩诺胡椒的批萨。

输入
输入文件pizza.in有若干行，描述了对一个批萨的约束。一个批萨约束由1到16个
口味约束组成，一个口味约束占一行，表示一位朋友的口味。最后一行仅含一个句
号"."，表示输入的结束。
一个口味约束是一组由分号";"结束的口味要求序列。
一个口味要求由一个符号（+/-）接着一个从A到P的大写字母组成。

输出
请将任一种符合要求的批萨的描述输出到文件pizza.out。一个批萨描述由一个长
度为10的字符串"Toppings: "开始（注意有一个空格），接着是一组按字母序排列
的字母，列出批萨的口味。例如，一个带有洋葱、凤尾鱼、鲜花椰菜和加拿大熏肉
的批萨描述为：
Toppings: ACFO
如果没有口味的组合可以满足每人至少一项请求，你的程序应输出字符串
"No pizza can satisfy these requests."

输入样例                输出样例
+A+B+C+D-E-F-G-H;       Toppings:
-A-B+C+D-E-F+G+H;
-A+B-C+D-E+F-G+H;
.

+A+B+C+D;               Toppings: CELP
+E+F+F+H;
+A+B-G;
+O+J-F;
+H+I+C;
+P;
+O+M+L;
+M-L+P;
.

+A+B+C+D;               No pizza can satisfy these requests.
+E+F+F+H;
+A+B-G;
+P-O;
+O+J-F;
+H+I+C;
+P;
+O;
+O+M+L;
-O-P;
+M-L+P;
.


--
※ 修改:．mk 于 May 13 10:03:56 修改本文．[FROM: 211.66.134.4]
发信人: Northming (必有谋猷裨帝右), 信区: ACMICPC
标  题: 第四届第二试第三题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:15:49 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第四届第二试第三题
发信站: 逸仙时空 Yat-sen Channel (Sun May 13 10:00:25 2001), 站内信件


第三题 UNIX的插头（40分）

可执行文件：plug.exe
输入文件：plug.in
输出文件：plug.out

你负责为联合国互联网执行组织(UNIX)的周年会议布置会议室。该组织的主旨，是
使互联网上的信息和思想的自由交流变得尽可能笨重和官僚（^_^）。

因为会议室被设计为招待来自世界各地的记者，它装备了一些电气插座以匹配各个
国家使用的电器的不同插头形状和电压。当然，这些插座的规格，是以这个会议室
建成时世界各国的规格作为标准的。不幸的是，由于这座会议室年代久远，它建成
时，记者还只是使用很少量的电子和电气设备，所以它对每种类型只配备了一个插
座。今天，像其它人一样，记者需要很多设备才能工作：掌上型计算器，手提电话
，录音机，寻呼机，电咖啡壶，微波炉，电吹风，电熨斗，电动牙刷，等等。自然
，这些设备当中有许多可以靠电池驱动的，但是看起来这个会议将会冗长乏味，所
以还是希望这些设备尽可能从插座供电。

在会议开始前，你将记者所有可能使用的设备集中起来，尝试将它们接到插座上。
你注意到有些设备的插头没有相应的插座。你怀疑这些设备来自一些在这座会议室
建成时还不存在的国家。对某些插座，也许有许多设备都使用对应的插头；而对另
一些插座，也许没有任何设备使用对应的插头。

为了解决这个问题，你走到附近一家五金电气商店。这家商店出售一些转接头，可
以将一种插头的转换成另一种插头。一个转接头还可以接到另一个转接头上。并非
所有插座和插头的组合都有相应的转接头，但是对每种出售的转接头，商店都有足
够的存货。

输入
输入文件plug.in有若干行。第一行是一个整数n（1≤n≤100），表示会议室的插
座数。接下来的n行列出了能在会议室找到的插座，每种插座的名称是由字母和数
字组成的字符串，长度不超过24个字符。接着一行是一个整数m（1≤m≤100），表
示你要连接的插头数。再接下来的m行列出了设备的名称和它使用的插头（与相应
插座的名称相同）。两者用一个空格分隔。每种设备的名称也是由字母和数字组成
的字符串，长度不超过24个字符。没有两个设备的名称完全相同。接着一行是一个
整数k（1≤k≤100），表示可用的转接头种类。接下来的k行每行描述了一种转接
头，首先给出转接头提供的插座，接着一个空格，接下来是插头的类型。

输出
请将最少的无法连接的设备数输出到文件plug.out。

输入样例        输出样例
4               1
A
B
C
D
5
laptop B
phone C
pager B
clock B
comb X
3
B X
X A
X D


--
发信人: Northming (必有谋猷裨帝右), 信区: ACMICPC
标  题: 第四届第二试第四题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:15:54 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第四届第二试第四题
发信站: 逸仙时空 Yat-sen Channel (Sun May 13 10:03:46 2001), 站内信件


第四题 街道的方向（40分）

可执行文件：street.exe
输入文件：street.in
输出文件：street.out

汽车碰撞监控（ACM）的一份报告指出，大部分严重车祸是在双行道上发生的。为
了减少车祸的伤亡，市长决定将尽可能多的街道改成单行道。你的任务是完成这项
工作，同时满足司机在任何一个路口，经过某条路线能到达其它任何一个路口。

你将收到这个城市的街道资料（所有的街道都是双行道）。每条街道连接两个路口
，并且不会穿越其它的路口。最多有四条街道汇集在同一个路口，而且任意两个路
口最多有一条街道连接。可能有某个路口只是某条街道的一端（即死胡同），也有
可能在改道完成后，仍有两个路口之间的路径所经过的街道全是双行道。

输入
输入文件street.in有若干行，第一行是两个用空格分隔的整数n和m，分别表示路
口数（1≤n≤1000）和街道数。路口从1到n进行编号。接下来的m行，每行包含两
个用空格分隔的整数i和j，表示连接路口i和j的街道。每条街道只出现一次，如果
街道i j出现过，则街道j i就不会再出现。

输出
请将改道的方案输出到文件street.out。对每条从路口i到j的单行道，输出一行
i j。对每条不能改成单行道的街道i j，分开两行输出i j和j i。街道的两个路口
用一个空格分隔。你可以用任何顺序输出街道。
注意：也许有多个符合题目要求的方案，你可以输出任何一个。

输入样例        输出样例
7 10            1 2
1 2             2 4
1 3             3 1
2 4             3 6
3 4             4 3
4 5             5 2
4 6             5 4
5 7             6 4
6 7             6 7
2 5             7 5
3 6

7 9             1 2
1 2             2 4
1 3             3 1
1 4             4 1
2 4             4 3
3 4             4 5
4 5             5 4
5 6             5 6
5 7             6 7
7 6             7 5


--
发信人: Northming (必有谋猷裨帝右), 信区: ACMICPC
标  题: 第四届第二试第五题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:16:00 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第四届第二试第五题
发信站: 逸仙时空 Yat-sen Channel (Sun May 13 10:06:12 2001), 站内信件


第五题 逻辑岛（40分）

可执行文件：island.exe
输入文件：island.in
输出文件：island.out

逻辑岛上有三种居民：天使（divine）永远说真话，魔鬼（evil）永远说谎话，人
类（human）白天说真话，晚上说谎话。岛上每个居民都知道其它居民的身份。
一个社会科学家来到逻辑岛。因为他无法从居民的相貌区分她们的身份，他希望你
能设计一个通讯分析器，从居民之间的谈话中推导一些事实。他感兴趣的事实是当
时是白天还是晚上，以及说话者是何种居民。

输入
输入文件island.in有若干行，第一行是一个整数n，表示对话包含的句子数。接下
来的n行，每行包含一句居民的话。每句话由说话者的名称（A，B，C，D，E五个大
写字母之一）开始，接着一个冒号"："和一个空格，接下来是下面三种句子之一：

o I am [not] ( divine | human | evil | lying ).
o X is [not] ( divine | human | evil | lying ).
o It is ( day | night ).

方括号[]表示括号中的单词可以出现也可以不出现，圆括号（）表示由|分隔的若
干项之一必须出现。X是A，B，C，D，E五个名称之一。句子当中不会出现两个连续
的空格。对话中最多有50个句子。

输出
请将能够推导的事实输出到文件island.out。如果根据规则不可能发生这样的对话
，请输出"This is impossible."。如果无法推导出任何事实，请输出"No facts
are deducible."。否则请按照下面的格式输出所有能够推导的事实：
o X is ( divine | human | evil ).
o It is ( day | night ).
X应当替换为相应说话者的名称。请先按字母序输出关于居民身份的事实，然后是
关于白天黑夜的事实。
输出时，事实的前后应当都没有空格，事实当中也不会出现两个连续的空格。

输入样例                输出样例
1
A: I am divine.         No facts are deducible.
1
A: I am lying.          This is impossible.
1
A: I am evil.           A is human.
                        It is night.
3
A: B is human.          A is evil.
B: A is evil.           B is divine.
A: B is evil.

提示
为了使你更好地理解推理的过程，我们来解释一下第三个样例的推理。A说"I am
evil."从中能推导出什么？显然，A不可能是天使，否则她就在说谎；类似的，A也
不可能是魔鬼，否则她就在说真话。所以，A一定是人类，而且，由于她在说谎，
当时一定是晚上。所以正确的输出如样例所示。
在第四个样例里，显然A在说谎，因为她的话前后矛盾。所以B既不是人类也不是魔
鬼，因此B一定是天使。B永远说真话，所以A一定是魔鬼。哈哈！


--

--
撷取生活中每一朵清新的浪花,智慧的浪花 ..汇成音乐的海洋.

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]