Algorithm 版 (精华区)

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

发信人: superhyb (CS99+:不惊暈..), 信区: ACMICPC
标  题: 第一试第一题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:49:02 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第一试第一题
发信站: 逸仙时空 Yat-sen Channel (Fri May 11 18:43:53 2001), 站内信件

第一题：循环节（repeating cycle）（30分）

问题描述：
求一个分数对应的十进制小数的循环节。我们定义一个小数的循环节是它的第一个最短
的向右无限循环的数字串。
下面是一些分数的循环节，循环节部分用括号括住，例如：
分数    十进制小数      循环节  循环节长度（位数）
1／6    0.1(6)          6       1
5／7    0.(714285)      714285  6
1／250  0.004(0)        0       1

输入：输入文件的每行包含两个正整数，第一个为分子，第二个为分母，它们之间用一
个空格隔开，这两个正整数值均不超过3000，输入以00结束。

输出：输出到屏幕。对应输入的每一行，有两行输出，其中第一行输出一个分数和它的
小数表示，其中小数由非循环节部分加上第一个出现的循环节或者不大于50位的小数，
第二行输出整个循环节的长度，如小数超过50位仍未出现循环节则认为循环节长度为0。

输入样例：  输出样例：
1 6         1／6＝0.1(6)
5 7         1
1 250       5/7=0.(714285)
00          6
            1/250=0.004(0)
            1


--
发信人: superhyb (CS99+:不惊暈..), 信区: ACMICPC
标  题: 第一试第二题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:49:08 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第一试第二题
发信站: 逸仙时空 Yat-sen Channel (Fri May 11 18:44:53 2001), 站内信件

第二题  拼字游戏  (word crosses)  （30分）

拼字游戏历史悠久，能锻炼人的思维和提高单词记忆量。在欧美报纸的版面中经常会见
到。本题只是简单地演示单组交叉词。所谓单组交叉词，是指两个单词交叉放置，一个
水平放置，另一个垂直放置，交叉点是两个单词都共用一个字母，而且交叉点遵循交叉
靠前原则，即这公用的字母尽量在水平单词的前方，然后也尽量在垂直单词的上方。例
如：DEFER，PREFECT（前一个为水平单词）的交叉点是E，而PREFECT，EDFER的交叉点是
R。双交叉词是指有两组单组交叉词，它们的水平单词放在同一行。
试编程将输入的每四个一组的单词尽可能组成双交叉词。

输入：输入文件由若干行组成，每行有四个单词，按顺序每两个为一组，每组第一个单
词为水平单词，每个单词由1到10个大写字母组成，单词之间用一个空格隔开。最后一行
由一个"＃"结束。

输出：输出文件由一系列双交叉词组成，每个水平单词之间隔三个空格。若不能构成双
交叉词，则显示"Unable to make two crosses"。每组双交叉词间空一行。

输入样例：
AT  PART  RIGHT  BUT
PEANUT  BANANA  VACUUM  GREEDY
＃

输出样例：
         B
P        U
AT   RIGHT
R
T

Unable to make two crosses


--
发信人: superhyb (CS99+:不惊暈..), 信区: ACMICPC
标  题: 第一试第三题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:49:14 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第一试第三题
发信站: 逸仙时空 Yat-sen Channel (Fri May 11 18:45:22 2001), 站内信件

第三题：车厢重组（40分）

  在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站
的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢
的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车
厢按车厢号从小到大重新排列。他退休之后，火车站决定将这一工作自动化，其中一项
重要的工作是编一个程序，从键盘输入初始的车厢顺序，计算最少用多少步就能将车厢
排序，屏幕输出最少的步数。

输入样例：
4 3 2 1

输出样例：
6


--
发信人: superhyb (CS99+:不惊暈..), 信区: ACMICPC
标  题: 第一试第四题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:49:22 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第一试第四题
发信站: 逸仙时空 Yat-sen Channel (Fri May 11 18:46:04 2001), 站内信件

第四题  Internet消息发布  （50分）

问题描述：设Internet上有N个站点，通常从一个站点发送消息给其他
N－1个站点，需依次发送N－1次。这样从一个站点发布消息传遍N个站点时，可能要较长
时间。而当一个站点发布消息给另一个站点后，已获得消息的这两个站点就可以同时发
布消息给另外两个站点，此后就有四个站点可以同时发布消息，这种发布消息方法应该
会缩短消息传遍N个站点的时间。
请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出从
第一个站点开始发布消息传遍N个站点的最短时间。

输入：由文件Internet.dat输入数据，文件的第一行是Internet上的站点数N（1<=N<=1
0000），第二行起是邻接矩阵严格的下三角部分，各行是整数或字符X。A(I, J)表示从
I站点发送消息给J站点所需要的时间。假设网络是无方向的，故A(I, J)＝A(J, I)，当
A(I, J)＝X时，表示从站点I不能直接向站点J发送消息；A(I, I)＝0表示没有必要自己
给自己送消息（1<=I<=N），严格的下三角阵表示如下：
A(2, 1)
A(3, 1), A(3, 2)
A(4, 1), A(4, 2), A(4, 3)
┇
A(N, 1), A(N, 2)……A(N, N-1)
文件名由键盘输入。

输出：从屏幕上输出，输出只有一行，它是一个非负整数，若为0表示无解，非0表示合
符题意的最小整数。

输入样例：
5
50
30   5
100 20  50
10 X X  10

输出样例：
35


--
发信人: superhyb (CS99+:不惊暈..), 信区: ACMICPC
标  题: 第一试第五题
发信站: 逸仙时空 Yat-sen Channel (Sat Jun  9 23:49:27 2001), 站内信件

发信人: mk (逐风), 信区: Programming
标  题: 第一试第五题
发信站: 逸仙时空 Yat-sen Channel (Fri May 11 18:46:50 2001), 站内信件

第五题  01串（01  Sequence）（50分）

给定7个整数N，A0，B0，L0，A1，L1，要求设计一个01串S1S2S3…Si…SN，
满足：
1．Si =0或Si =1，1<=i<=N；
2．对于S的任何连续的长度为L0的子串SjSj＋1…Sj＋L0－1（1<=j<=N-L0+1），0的个数
大于等于A且小于等于B；
3．对于S的任何连续的长度为L1的子串SjSj＋1…Sj＋L0－1（1<=j<=N-L0+1），1的个数
大于等于A1且小于等于B1；
例如：N＝6，A0＝1，B0＝2，L0＝3，A1＝1，B1＝1，L1＝2，则存在一个满足上述所有
条件的01串S＝010101。

输入：从文件Sequence.dat输入，每个文件仅一行，有7个整数，依次表示N，A0，B0，
L0，A1，B1，L1（3<=N<=1000，1<=A0<=B0<=L0<=N，1<=A1<=B1<=L1<=N），相邻两个整
数之间用一个空格分隔。

输出：屏幕输出，仅一行，若不存在满足所有条件的01串，则输出一个整数－1，否则输
出一个满足所有条件的01串。

输入样例：
6  1  2  3  1  1  2

输出样例：
010101


--

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

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