1
湖南省首届“湘邮科技杯”大学生程序设计大赛试题
试题 1 n 个人围成一圈,并依次编号 1～ n,。从编号为 1 的人开始，按顺时针方向每隔一人选出一个，
剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个幸运儿，请问开始时应该站在什么位置？（设 3<=n<=50）
输入,开始时的人数 n
输出,第 1 行是选出顺序，第 2 行是两名幸运儿的开始位置（按升序排列）,位置编号之间用一个空格分开。
示例
输入,
12
应该的输出,
2 4 6 8 10 12 3 7 11 5
1 9
试题 2 在二维字符阵列中寻找指定的字符串。
输入,前两行分别指示字符矩阵的宽 w 和高 h（ 1<=w<=80 且 1<=h<=80） 。接下来的 h 行每行 w 个字符便是字符矩阵的内容，再下面的 1 行为要寻找的字符串的数目 n（ n<10）,其后的 n 行便是要寻找的字符串，每个字符串不会超过 20 个字符。
输出,n 行，每行保存 1 个字符串的位置。位置的格式形如 (1,2)->(2,6)，意为该字符串首字母在字符矩阵中的位置是第 1 列 2 行，尾字母在字符矩阵中的位置是第 2 列 6 行。
备注,如果某个字符串在字符阵列中出现多次，则只记录任意一个出现位置即可。字符串出现的形式可能是水平、竖直、向前、向后和斜向。输出的位置顺序应该与输入中的字符串出现顺序一致。
区分字符的大小写。
2
示例
输入,
输出,
(1,3)->(5,7)
(6,1)->(1,1)
(7,7)->(7,1)
试题 3 给出一个正方形图案和它的变换图案，称为图案变换对。编写程序，求图案变换对之间的最小变换。图案是由黑白两种小方块构成的。可能的变换包括,
(1) 旋转 90 度：图案顺时针旋转 90 度，记做 rot90
(2) 旋转 180 度：图案顺时针旋转 180 度，记做 rot180
(3) 旋转 270 度：图案顺时针旋转 270 度，记做 rot270
(4) 竖直映像：图案以其上方的一条平行线为轴翻转，记做 vr
(5) 联合变换：图案首先做一次竖直映像变换，然后做一次旋转变换，记做 vr-rot90 或 vr-rot180 或
vr-rot270
(6) 保持：图案和变换后的图案完全一样，记做 idt
(7) 错误：无法应用上述变换将初始图案变换成它的变换图案，记做 imp
输入,输入文件中包含多组图案变换对。每一对图案数据的起始行都是一个整数，表示正方形图案的边长 a（以一个小方块为单位,1<=a<=100）,后续的 a 行，每一行包含了原图案的一行和变换图案的对应行，两者之间用一个空格分开。黑色小方块用 b 表示，白色小方块用 o 表示。
输出,输出文件的每一行对应输入文件的每一个图案变换对。其中每行开始的整数表示对应图案对在输入文件中出现的序号，紧跟一个空格，然后就是该图案对的最小变换，采用上述记号表示。
备注,为了比较不同变换的大小，定义：旋转变换的代价小于映像变换，小角度旋转变换的代价小于大角度旋转变换，保持变换的代价最小。注意：对本题而言，只有上面列出的变换是合法的，如果某个图案对可以由多个变换得到，则应选择代价最小的变换。
3
示例
输入,
5
booob oooob
obooo ooobo
ooobo obooo
oobob ooboo
oooob bboob
6
oooobb boooob
oooboo bobooo
bboobo oboobo
oobooo ooobob
oooboo oobooo
ooboob oobooo
2
bo bo
ob ob
4
oobo ooob
bboo oooo
oooo bboo
ooob oobo
5
boooo obooo
obooo ooboo
obooo ooboo
ooobo oooob
oooob boooo
4
oboo oobo
obob booo
oooo oobb
oobo oooo
2
oo bb
bb oo
输出,
1 rot90
2 rot270
3 idt
4 vr
5 imp
6 vr-rot270
7 rot180
4
试题 4 在计算机辅助设计(CAD)中，有一个经典问题：消除隐藏线（被其它图形遮住的线段） 。你需要设计一个软件，帮助建筑师绘制城市的侧视轮廓图。为了方便处理，限定所有的建筑物都是矩形的，
而且全部建立在同一水平面上。每个建筑物用一个三元组表示（Li,Hi,Ri）其中 Li 和 Ri 分别是建筑物 i 的左右边缘坐标，Hi 是建筑物 i 的高度。
下面左图中的建筑物分别用如下三元组表示,
(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)
下面右图中的城市侧视轮廓线用如下的序列表示,
（1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0）
输入,输入文件中包含一系列的建筑物三元组。建筑物的坐标都是正整数且不大于 1000。建筑物的数目不会超过 50。每行只有一个三元组。三元组的每个元素之间用一个空格分开。三元组按照 Li 排序，
即左边缘坐标最小的建筑物三元组会出现在输入文件的第一行。
输出,输出文件中包含一行描述轮廓线的数值序列，其中偶元素代表轮廓线的延伸高度，奇元素代表轮廓线顶点的水平坐标，如上面的图例所示。
示例
输入,
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
输出,
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
5
试题 5 也许是因为有 10 个手指的原因，所以我们把 0～ 9 十个数字组合起来表达任意的数值，但这并不是唯一可能的记数法。在某个外星球居住着一种智慧生物，他们的手跟我们的手构造不同，他们的记数法也很奇特。他们用三个记号 ’0’,’1’,’-’的组合来表达数值，这三个记号分别对应数值 0,1,-1。在他们的数值系统中，每个数位是右边相邻数位的 3 倍。因此数 ’10-’表示数值 8（因为 8＝ 1× 9＋ 0× 3
＋－ 1× 1）,数 ’-1’表示数值 -2（因为 -2= -1× 3＋ 1× 1） 。
编写程序，读入一组 -2
31
至 2
31
－ 1 之间的数值，输出对应的外星球数值表示。
输入,每行一个 10 进制数值
输出,每行一个与输入文件对应的外星球数值表示
示例
输入,
10
2
-17
42
1024
-2147483648
输出,
101
1-
-101
1---0
111-0-1
-10110100011---1-1--1
试题 6 逻辑表达式有如下形式,
（ 1）原子式，用一个区分大小写的字母表示；
（ 2）组合式；若 A 和 B 是逻辑表达式，则 (A|B)也是，意为,A 或 B” ； (A&B)意为,A 和 B” ；
~A 意为“非 A” ； (A->B)意为,A 推出 B”,或等价的,B 或非 A” 。
以上表达式的形式是固定的，其中的括号不能缺少，且字符间没有空格。
对于某个逻辑表达式，如果变换其中原子式的取值（真或假）,该表达式的整体取值可能为真，则称这样的逻辑表达式是可满足的，否则是不可满足的。比如下面的表达式都是可满足的,
q
(a|(b&c))
((a&~a)->z)
而这些是不可满足的,
(q&~q)
(((a|~b)&(~a|b))&(a&~b))
6
编写程序，判断某个逻辑表达式的可满足性。
输入,每一行都是一个逻辑表达式（整个表达式最多 10 个原子式，且不超过 150 个字符）
输出,每行包含一个字符,’y’表示输入文件对应行中的逻辑表达式是可满足的，或者 ’n’表示输入文件对应行中的逻辑表达式是不可满足的；
示例
输入,
q
(a|(b&c))
((a&~a)->z)
(q&~q)
(((a|~b)&(~a|b))&(a&~b))
输出,
y
y
y
n
n
试题 7 一家银行希望采用光学字符识别系统自动读出支票中的账号，组成账号的每个数字都是 7 段数位体。一种图象处理软件可以将组成数字的横段和竖段分别转换成 ASCII 码中的竖线‘|’和下划线
‘_’。如果显示正常，则 10 个数字的序列应该具有如下形态,
支票中的账号有 9 位数字，但由于光学扫描装置可能会漏检某些数位段，所以 9 位数字未必都能正确地被扫描转换成对应的 ’|’ ’_’字符形式。为了容错和纠错，对于一个 9 位账号 d9d8…d1，设定其校验条件为,
(d1+2d2+3d3+…+9d9) mod 11 = 0
你需要设计一个程序，从扫描转换的结果推测原始的账号，假定,
(1) 若经扫描转换的某组数字全部保存了正确的数字形式而且满足校验条件，则该组数字就是原始的账号；
(2) 9 位数中最多只有一位在扫描转换中失去正确的数字形式；
(3) 扫描转换不会引入额外的数位段。
当检测到数位段时，扫描转换程序将输出 ASCII 码的 ’|’或 ’_’；当检测到空白区域时，将输出 ’.’。比如下面的扫描转换结果,
7
正确的推测值是 123456789，其中的第 2 位经扫描转换后失去正确的数字形式，既像 2 又像 3，如果令其为 3 则与校验条件冲突；其中的第 5 位虽然保存了正确的数字形式，但既可能是 5 也可能是 6，但如果令其为 6，则与上面的假定 2 冲突。
输入,输入文件中包含一组用 ASCII 字符表示的账号。每个账号占 3 行，每位数字占 3 列，每行 27
个字符。没有空行，也没有空格。
输出,每行代表一个账号的推测值。账号的顺序和数目与输入文件一致。如果没有找到合理值，则输出 ’failure’；如果找到多个合理的推测，则输出 ’ambiguous’。
示例
输入,
输出,
123456789
ambiguous
failure
878888888
试题 8 我军特工探知了敌军的信息加密方式，但尚未获得密钥。已知敌军所有的信息都是码值在 1－
127 之内的 ASCII 字符。敌军以 5 个字符为单位加密信息。设 p0p1p2p3p4 是 5 个待加密的字符，敌军将这 5 个字符与另外 9 个密钥 k0,…,k8 混合起来产生对应的 5 个整数型密文 e0,…,e4。已知这 9 个密钥也是码值在 1－ 127 间的 ASCII 字符。其混合原则如下,
我军特工以生命为代价换来了一小串明文和对应的密文。你的任务是找到密钥，并破解另一组被我军截获的敌军密文。
8
输入,第一行是一串大于 10 个字符的明文。第二行是明文中前 5 个字符对应的密文，分别是用空格分开的 5 个整数；第三行是明文中第 6 个到第 10 个字符对应的密文，分别是用空格分开的 5 个整数。然后是一个空行。后续的每一行都是用空格分开的 5 个整数，代表需要你破解的 5 个密文字符。
输出,按顺序给出输入文件中需要你破解的密文对应的明文。
备注,已知 10 个明文字符和对应的密文就足以找到密钥。
示例
输入,
John Q,Crackjack
30096 28880 32662 34217 36518
22426 23187 28934 27877 29942
34391 35683 39956 40657 45237
33044 30700 34923 37133 38330
37200 37645 43055 43698 47491
32574 30389 35225 36978 38050
输出,
Squeamish ossifrage,
湖南省首届“湘邮科技杯”大学生程序设计大赛试题
试题 1 n 个人围成一圈,并依次编号 1～ n,。从编号为 1 的人开始，按顺时针方向每隔一人选出一个，
剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个幸运儿，请问开始时应该站在什么位置？（设 3<=n<=50）
输入,开始时的人数 n
输出,第 1 行是选出顺序，第 2 行是两名幸运儿的开始位置（按升序排列）,位置编号之间用一个空格分开。
示例
输入,
12
应该的输出,
2 4 6 8 10 12 3 7 11 5
1 9
试题 2 在二维字符阵列中寻找指定的字符串。
输入,前两行分别指示字符矩阵的宽 w 和高 h（ 1<=w<=80 且 1<=h<=80） 。接下来的 h 行每行 w 个字符便是字符矩阵的内容，再下面的 1 行为要寻找的字符串的数目 n（ n<10）,其后的 n 行便是要寻找的字符串，每个字符串不会超过 20 个字符。
输出,n 行，每行保存 1 个字符串的位置。位置的格式形如 (1,2)->(2,6)，意为该字符串首字母在字符矩阵中的位置是第 1 列 2 行，尾字母在字符矩阵中的位置是第 2 列 6 行。
备注,如果某个字符串在字符阵列中出现多次，则只记录任意一个出现位置即可。字符串出现的形式可能是水平、竖直、向前、向后和斜向。输出的位置顺序应该与输入中的字符串出现顺序一致。
区分字符的大小写。
2
示例
输入,
输出,
(1,3)->(5,7)
(6,1)->(1,1)
(7,7)->(7,1)
试题 3 给出一个正方形图案和它的变换图案，称为图案变换对。编写程序，求图案变换对之间的最小变换。图案是由黑白两种小方块构成的。可能的变换包括,
(1) 旋转 90 度：图案顺时针旋转 90 度，记做 rot90
(2) 旋转 180 度：图案顺时针旋转 180 度，记做 rot180
(3) 旋转 270 度：图案顺时针旋转 270 度，记做 rot270
(4) 竖直映像：图案以其上方的一条平行线为轴翻转，记做 vr
(5) 联合变换：图案首先做一次竖直映像变换，然后做一次旋转变换，记做 vr-rot90 或 vr-rot180 或
vr-rot270
(6) 保持：图案和变换后的图案完全一样，记做 idt
(7) 错误：无法应用上述变换将初始图案变换成它的变换图案，记做 imp
输入,输入文件中包含多组图案变换对。每一对图案数据的起始行都是一个整数，表示正方形图案的边长 a（以一个小方块为单位,1<=a<=100）,后续的 a 行，每一行包含了原图案的一行和变换图案的对应行，两者之间用一个空格分开。黑色小方块用 b 表示，白色小方块用 o 表示。
输出,输出文件的每一行对应输入文件的每一个图案变换对。其中每行开始的整数表示对应图案对在输入文件中出现的序号，紧跟一个空格，然后就是该图案对的最小变换，采用上述记号表示。
备注,为了比较不同变换的大小，定义：旋转变换的代价小于映像变换，小角度旋转变换的代价小于大角度旋转变换，保持变换的代价最小。注意：对本题而言，只有上面列出的变换是合法的，如果某个图案对可以由多个变换得到，则应选择代价最小的变换。
3
示例
输入,
5
booob oooob
obooo ooobo
ooobo obooo
oobob ooboo
oooob bboob
6
oooobb boooob
oooboo bobooo
bboobo oboobo
oobooo ooobob
oooboo oobooo
ooboob oobooo
2
bo bo
ob ob
4
oobo ooob
bboo oooo
oooo bboo
ooob oobo
5
boooo obooo
obooo ooboo
obooo ooboo
ooobo oooob
oooob boooo
4
oboo oobo
obob booo
oooo oobb
oobo oooo
2
oo bb
bb oo
输出,
1 rot90
2 rot270
3 idt
4 vr
5 imp
6 vr-rot270
7 rot180
4
试题 4 在计算机辅助设计(CAD)中，有一个经典问题：消除隐藏线（被其它图形遮住的线段） 。你需要设计一个软件，帮助建筑师绘制城市的侧视轮廓图。为了方便处理，限定所有的建筑物都是矩形的，
而且全部建立在同一水平面上。每个建筑物用一个三元组表示（Li,Hi,Ri）其中 Li 和 Ri 分别是建筑物 i 的左右边缘坐标，Hi 是建筑物 i 的高度。
下面左图中的建筑物分别用如下三元组表示,
(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)
下面右图中的城市侧视轮廓线用如下的序列表示,
（1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0）
输入,输入文件中包含一系列的建筑物三元组。建筑物的坐标都是正整数且不大于 1000。建筑物的数目不会超过 50。每行只有一个三元组。三元组的每个元素之间用一个空格分开。三元组按照 Li 排序，
即左边缘坐标最小的建筑物三元组会出现在输入文件的第一行。
输出,输出文件中包含一行描述轮廓线的数值序列，其中偶元素代表轮廓线的延伸高度，奇元素代表轮廓线顶点的水平坐标，如上面的图例所示。
示例
输入,
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
输出,
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
5
试题 5 也许是因为有 10 个手指的原因，所以我们把 0～ 9 十个数字组合起来表达任意的数值，但这并不是唯一可能的记数法。在某个外星球居住着一种智慧生物，他们的手跟我们的手构造不同，他们的记数法也很奇特。他们用三个记号 ’0’,’1’,’-’的组合来表达数值，这三个记号分别对应数值 0,1,-1。在他们的数值系统中，每个数位是右边相邻数位的 3 倍。因此数 ’10-’表示数值 8（因为 8＝ 1× 9＋ 0× 3
＋－ 1× 1）,数 ’-1’表示数值 -2（因为 -2= -1× 3＋ 1× 1） 。
编写程序，读入一组 -2
31
至 2
31
－ 1 之间的数值，输出对应的外星球数值表示。
输入,每行一个 10 进制数值
输出,每行一个与输入文件对应的外星球数值表示
示例
输入,
10
2
-17
42
1024
-2147483648
输出,
101
1-
-101
1---0
111-0-1
-10110100011---1-1--1
试题 6 逻辑表达式有如下形式,
（ 1）原子式，用一个区分大小写的字母表示；
（ 2）组合式；若 A 和 B 是逻辑表达式，则 (A|B)也是，意为,A 或 B” ； (A&B)意为,A 和 B” ；
~A 意为“非 A” ； (A->B)意为,A 推出 B”,或等价的,B 或非 A” 。
以上表达式的形式是固定的，其中的括号不能缺少，且字符间没有空格。
对于某个逻辑表达式，如果变换其中原子式的取值（真或假）,该表达式的整体取值可能为真，则称这样的逻辑表达式是可满足的，否则是不可满足的。比如下面的表达式都是可满足的,
q
(a|(b&c))
((a&~a)->z)
而这些是不可满足的,
(q&~q)
(((a|~b)&(~a|b))&(a&~b))
6
编写程序，判断某个逻辑表达式的可满足性。
输入,每一行都是一个逻辑表达式（整个表达式最多 10 个原子式，且不超过 150 个字符）
输出,每行包含一个字符,’y’表示输入文件对应行中的逻辑表达式是可满足的，或者 ’n’表示输入文件对应行中的逻辑表达式是不可满足的；
示例
输入,
q
(a|(b&c))
((a&~a)->z)
(q&~q)
(((a|~b)&(~a|b))&(a&~b))
输出,
y
y
y
n
n
试题 7 一家银行希望采用光学字符识别系统自动读出支票中的账号，组成账号的每个数字都是 7 段数位体。一种图象处理软件可以将组成数字的横段和竖段分别转换成 ASCII 码中的竖线‘|’和下划线
‘_’。如果显示正常，则 10 个数字的序列应该具有如下形态,
支票中的账号有 9 位数字，但由于光学扫描装置可能会漏检某些数位段，所以 9 位数字未必都能正确地被扫描转换成对应的 ’|’ ’_’字符形式。为了容错和纠错，对于一个 9 位账号 d9d8…d1，设定其校验条件为,
(d1+2d2+3d3+…+9d9) mod 11 = 0
你需要设计一个程序，从扫描转换的结果推测原始的账号，假定,
(1) 若经扫描转换的某组数字全部保存了正确的数字形式而且满足校验条件，则该组数字就是原始的账号；
(2) 9 位数中最多只有一位在扫描转换中失去正确的数字形式；
(3) 扫描转换不会引入额外的数位段。
当检测到数位段时，扫描转换程序将输出 ASCII 码的 ’|’或 ’_’；当检测到空白区域时，将输出 ’.’。比如下面的扫描转换结果,
7
正确的推测值是 123456789，其中的第 2 位经扫描转换后失去正确的数字形式，既像 2 又像 3，如果令其为 3 则与校验条件冲突；其中的第 5 位虽然保存了正确的数字形式，但既可能是 5 也可能是 6，但如果令其为 6，则与上面的假定 2 冲突。
输入,输入文件中包含一组用 ASCII 字符表示的账号。每个账号占 3 行，每位数字占 3 列，每行 27
个字符。没有空行，也没有空格。
输出,每行代表一个账号的推测值。账号的顺序和数目与输入文件一致。如果没有找到合理值，则输出 ’failure’；如果找到多个合理的推测，则输出 ’ambiguous’。
示例
输入,
输出,
123456789
ambiguous
failure
878888888
试题 8 我军特工探知了敌军的信息加密方式，但尚未获得密钥。已知敌军所有的信息都是码值在 1－
127 之内的 ASCII 字符。敌军以 5 个字符为单位加密信息。设 p0p1p2p3p4 是 5 个待加密的字符，敌军将这 5 个字符与另外 9 个密钥 k0,…,k8 混合起来产生对应的 5 个整数型密文 e0,…,e4。已知这 9 个密钥也是码值在 1－ 127 间的 ASCII 字符。其混合原则如下,
我军特工以生命为代价换来了一小串明文和对应的密文。你的任务是找到密钥，并破解另一组被我军截获的敌军密文。
8
输入,第一行是一串大于 10 个字符的明文。第二行是明文中前 5 个字符对应的密文，分别是用空格分开的 5 个整数；第三行是明文中第 6 个到第 10 个字符对应的密文，分别是用空格分开的 5 个整数。然后是一个空行。后续的每一行都是用空格分开的 5 个整数，代表需要你破解的 5 个密文字符。
输出,按顺序给出输入文件中需要你破解的密文对应的明文。
备注,已知 10 个明文字符和对应的密文就足以找到密钥。
示例
输入,
John Q,Crackjack
30096 28880 32662 34217 36518
22426 23187 28934 27877 29942
34391 35683 39956 40657 45237
33044 30700 34923 37133 38330
37200 37645 43055 43698 47491
32574 30389 35225 36978 38050
输出,
Squeamish ossifrage,
