Algorithm 版 (精华区)

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

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

发信人: mk (逐风), 信区: Programming
标  题: 第四届第一试第一题
发信站: 逸仙时空 Yat-sen Channel (Sat May 12 16:30:48 2001), 站内信件


第一题 识别浮点常量（40分）
可执行文件：identify.exe
输入方式：键盘输入
输出方式：屏幕输出

编译器在对程序进行编译之前，首先要进行语法分析。通常，程序被分解成若干个
小单元，然后和语言的语法模式进行匹配。在分析表达式的时候，变量的类型在变
量声明的时候就决定了；而常量的类型需要从常量的形式来判断。

假设你是自动编译机器（ACM）开发小组的一员，负责Pascal语言编译器的开发。
你的任务是分析程序分解模块送来的文件，判断其中包含的字符串是否合乎语法的
Pascal浮点常量。

Pascal语言对浮点常量的语法要求是：一个浮点常量除了十进制数码之外，必须带
有一个小数点或/和一个指数（紧接在字母e或E之后，在正式文档中也被称为比例
因子）。如果该浮点常量含有小数点，则在小数点两侧都至少要有一个十进制数码
。当然，在整个浮点常量或/和指数之前，也许会出现符号+或-。指数不能包含小
数。空格也许会出现在浮点常量的前后，但不会出现在浮点常量中间。

请注意Pascal语言的语法规则没有对浮点常量的取值范围做出任何假定。

输入
输入只有一行，就是有待识别的字符串。字符串的长度不超过255。

输出
请将分析的结果按以下样例的格式输出。如果输入文件中的字符串是Pascal浮点常
量，请输出字符串"YES"，否则输出字符串"NO"。

输入样例        输出样例
1.2             YES
1.              NO
1.0e-55         YES
e-12            NO
1e-12           YES
6.5E            NO
+4.1234567890E-99999    YES


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

发信人: mk (逐风), 信区: Programming
标  题: 第四届第一试第二题
发信站: 逸仙时空 Yat-sen Channel (Sat May 12 16:32:07 2001), 站内信件


第二题 版本大混乱？（40分）
可执行文件：versions.exe
输入方式：键盘输入
输出方式：屏幕输出

    计算机软件是生命期最短的消费品之一。对商业软件来说，每年发布一个新的
软件版本看起来是合适的。在版本1.0之后，我们有版本2.0，接着是版本2.1，3.
0，等等。公共软件，例如GNU软件，或Liunx，它们更新生命周期甚至更短--可能
每天都有一个新版本出现。

    版本号通常被用来区分一种软件包在不同时间的发布。大部分软件版本号都是
用"."分隔的非负整数的序列。对两个不同的版本A=a1.a2.….an和B=b1.b2.….bm
，如果下面两个条件之一成立，我们认为版本A要比B新：

1. 对某个i，我们有：对所有j<i，ai>bi和aj=bj；

2. n比m大，而且对所有i<=m，ai=bi。

    在这个问题里，你要对给定的一组版本号按照上面的定义从旧到新排序。

输入
    输入包含若干行，第一行是一个整数n（n<=20），表示要排序的版本数。接下
来的n行，每行包含一个版本号。每个版本号是一个长度不超过50的字符串。你可
以认为版本号都符合上面的定义。

输出
    将排序的结果按以下样例的格式输出。

输入样例
4
3.0.5
1
2.4
2.4.6

输出样例
1
2.4
2.4.6
3.0.5


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

发信人: mk (逐风), 信区: Programming
标  题: 第四届第一试第三题
发信站: 逸仙时空 Yat-sen Channel (Sat May 12 16:33:41 2001), 站内信件

第三题 锦标赛（40分）
可执行文件：seeding.exe
输入方式：键盘输入
输出方式：屏幕输出

在许多竞赛当中，选手们被赋予种子排名代表他们的相对实力，最优秀那个选手的
种子排名是1，其次那个选手的种子排名是2，依次类推。在安排一个淘汰赛制的锦
标赛赛程时，总是要求最优秀的选手尽可能迟点碰头（例如，直到最后一轮比赛才
有可能看到1号种子和2号种子比赛）。

为了说明赛程的安排规则，我们来定义两个名词。一场比赛的"实力"是比赛双方选
手的种子排名之和。假如最好的两个选手都能顺利晋级而在某场比赛碰头，我们就
称该场比赛的"实力"是"最佳实力"（换句话说，一场比赛的"最佳实力"就是可能参
加该场比赛的两个选手的种子排名之和的最小值）。

一个有n名选手参加的锦标赛总共需要进行r=ceil(log2 n)（ceil即进1取整) 轮比赛。
如果我们称决赛是第r轮，半决赛是第r-1轮，…，则赛程的安排规则可以描述如下：
在第k轮的所有比赛的"最佳实力"都是2r-k+1+1。举例来说，一个有13名选手参加的
锦标赛赛程如下图所示：

                         |
             +-----------+-------------+                第四轮
             |                         |
       +-----+-----+             +-----+-----+          第三轮
       |           |             |           |
    +--+-+      +--+---+      +--+--+     +--+-+        第二轮
    |    |      |      |      |     |     |    |
    |  +-+-+  +-+-+  +-+-+    |   +-+-+   |  +-+-+      第一轮
    1  |   |  |   |  |   |    2   |   |   3  |   |
       8   9  4  13  5  12        7  10      6  11

你的任务是解决下面的问题：给出n和m的值，计算在一个有n名选手参加的锦标赛
当中，实力为m的比赛最早可能出现在第几轮。你可以假定赛程就是按照上面所描
述的方式安排的。

输入
输入只有一行，包含两个用空格分隔的整数n和m，其中2≤n≤100，m≥3。你可以
假设实力为m的比赛一定可能在某轮出现。

输出
请将计算的结果按以下样例的格式输出。

输入样例        输出样例
100 3           7
13 10           2



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

发信人: mk (逐风), 信区: Programming
标  题: 第四届第一试第四题
发信站: 逸仙时空 Yat-sen Channel (Sat May 12 16:34:42 2001), 站内信件

第四题 随机数（40分）
可执行文件：random.exe
输入文件：random.in
输出文件：random.out

在这个问题里，"黑箱"是一个简单的数据库。它可以保存一组整数，同时有一个特
殊的变量i，初始时黑箱是空的，而且i 的值是0。这个黑箱能够接收操作指令序列
并进行处理。有两种操作指令：

o ADD(x)：将整数x放入黑箱；

o GET：将i加1并输出黑箱所有整数中第i小的元素。所谓第i小的元素，是将黑箱
中的元素按非递减排序后，在第i个位置上的数。

我们来看看一个有11条操作指令的例子：

N       操作指令        i       执行指令后黑箱中的内容（元素按非递减排序）
涑?
1       ADD(3)          0       3
2       GET             1       3       3
3       ADD(1)          1       1,3
4       GET             2       1,3     3
5       ADD(-4)         2       -4,1,3
6       ADD(2)          2       -4,1,2,3
7       ADD(8)          2       -4,1,2,3,8
8       ADD(-1000)      2       -1000,-4,1,2,3,8
9       GET             3       -1000,-4,1,2,3,8        1
10      GET             4       -1000,-4,1,2,3,8        2
11      ADD(2)          4       -1000,-4,1,2,2,3,8

我们用两组整数去描述操作指令序列：

1．A(1),A(2),…,A(M)：输入黑箱的元素序列，A的值是绝对值不大于2,000,000,
000的整数，M≤30000。对应上面的例子，我们有A=(3,1,-4,2,8,-1000,2)。

2．u(1),u(2),…,u(N)：一个自然数序列，表示第一个，第二个，…，第N个GET操
作指令执行时黑箱中的元素个数。对应上面的例子，我们有u=(1,2,6,6)。

黑箱的算法要求自然数序列u(1),u(2),…,u(N)是非递减的，N≤M，并且对每个p（
1≤p≤N）不等式p≤u(p)≤M总是成立的。因为序列u中的第p个元素代表要执行一
个GET操作输出A(1),A(2),…,A(u(p))当中第p小的元素。

在为黑箱算法设计测试数据的时候我们遇到了下面的问题。普通的随机数发生器并
不适合用来产生随机序列{u(i)}。因为序列本身附加了某种限制，如果采用逐个生
成序列中的元素，每次选择的随机数都符合限制的方法，产生的序列从整体上说并
不是完全随机的。

我们发现这个问题可以用下面的方法解决。如果我们按字典序枚举所有满足要求的
序列并为每一个序列编号，只要我们产生一个随机数，对应的序列就相当于一个随
机的序列。乍一看好象只要写一个程序按字典序产生所有满足要求的序列就足够了
。仔细想想！即使M和N的值不是很大，要穷举这些序列也可能要花最先进的计算器
几个世纪的时间。但是只要我们能够根据编号立即产生所需的序列，就可以避免穷
举所有序列。

不过这仅仅是问题的一部分。因为序列的数量实在太多了，序列的编号也许是一个
很大的数字，甚至可能有上百位，远远超出普通的随机数发生器所能产生随机数的
范围。于是我们决定由一个[0,1]区间的随机实数产生一个很大的随机整数。具体
来说，将这个随机实数用二进制表示成：0.b1b2…，所有的bi=0或1。然后用下面
的公式将这样一个实数与[A,B]区间的一个整数联系起来：

G(A,B,0.b1b2…bp) =     p=0或A=B：A否则：b1=0：G(A,(A+B) div 2,0.b2b3…
bp)b1=1：G((A+B) div 2,B,0.b2b3…bp)
其中A≤B，p≥0，"div"表示整除。

给定M，N（1≤N≤M≤200）和一个二进制实数0.b1b2…bp（1≤p≤400），你的任
务是写一个程序找出G(1,T,0.b1b2…bp) 对应的u序列。更精确的说，令T表示对给
定的M和N所有满足要求的u序列总数，将这T个序列按字典序从1开始编号，你的程
序应找出编号为G(1,T,0.b1b2…bp)的u序列。下面的例子按字典序列出了M=4和
N=3时所有符合要求的序列。
1, 2, 3         （这里T=14）
1, 2, 4
1, 3, 3
1, 3, 4
1, 4, 4
2, 2, 3
2, 2, 4
2, 3, 3
2, 3, 4
2, 4, 4
3, 3, 3
3, 3, 4
3, 4, 4
4, 4, 4

输入
输入文件random.in有两行，第一行是两个用空格分隔的整数M和N，第二行包含二
进制实数0.b1b2…bp，这一行没有空格。

输出
请将对应的序列u(1),u(2),…,u(N)输出到文件random.out。输出的数字用空格和
/或回车分隔。

输入样例                                         输出样例
4 3 0.01101101011110010001101010001011010        2 2 4



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

发信人: mk (逐风), 信区: Programming
标  题: 第四届第一试第五题
发信站: 逸仙时空 Yat-sen Channel (Sat May 12 16:36:14 2001), 站内信件

第五题 推箱子游戏（40分）
可执行文件：pushing.exe
输入文件：pushing.in
输出文件：pushing.out

你玩过"推箱子"，或者称为"仓库管理员"的游戏吗？如果没玩过，不要紧，下面我
来解释一下这种游戏的玩法。

试想象你站在一个二维的仓库里，这个仓库由方格组成，每个方格或者是石头墙，
或者是空的。你可以向东、南、西或北一次走一格。像这样的移动称为"走"。

在某个空格中有一个箱子，它可以移到相邻的空格中，方法是你站在箱子的另一侧
的空格去推它。当你推动箱子以后，你就移动到箱子本来的位置。像这样的移动称
为"推"。这个箱子无法用推以外的方法移动。这就意味着如果你把箱子推到一个角
落里，你就再也没有办法把它移出这个角落了。

一个空格被标记为目的地。你的工作是将箱子推到目的地，推的过程可以用"走"和
"推"的序列来描述。因为箱子很重，你想尽量使推的次数最少。你能写一个程序找
出最佳的方案吗？

###########
#T##......#    S 你
#.#.#..####    # 石头墙
#....B....#    B 箱子
#.######..#    T 目的地
#.....S...#
###########

输入
输入文件pushing.in有若干行，第一行是两个用空格分隔的整数r和c（1≤r,c≤
20），分别表示仓库的行数和列数。接下来的r行，每行包含c个字符，每个字符代
表仓库的一格。一格石头墙用"#"表示，一个空格用"."表示。你的初始位置用"S"
表示，箱子的初始位置用"B"表示，目的地用"T"表示。

输出
请将"走"和"推"的序列输出到文件pushing.out。输出的序列应当使推的的次数最
少。如果有多个符合题目要求的序列，输出一个使总移动步数最少（"走"和"推"）
的序列。如果仍有多个序列，你可以选择任意一个输出。

"走"和"推"的序列是用由字母E、S、W、N、e、s、w和n组成的字符串。大写字母表
示"推"，小写字母表示"走"。不同的字母分别表示东、南、西和北。

如果不可能将箱子推到目的地，请输出"Impossible."

输入样例        输出样例
1 7
SB....T         EEEEE

1 7
SB..#.T         Impossible.

7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########     eennwwWWWWeeeeeesswwwwwwwnNN

8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T            swwwnnnnnneeesssSSS



--
※ 修改:．mk 于 May 12 16:42:34 修改本文．[FROM: 211.66.134.4]

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

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