|
 SGOI第九次竞赛试题
【要求】
参赛者必须在当日13：15之前按照试卷中要求的程序名、输入/输出文件名及格式，进行作答。将所有解答（源程序、EXE文件）和参赛者信息文本文件"name.txt"用WINZIP压缩后作为附件发送；压缩文件名为"参赛者姓名.zip",用电子邮件同时发给
sgoi@shuguang.net和zhuquanmin@163.com
收，并在邮件的主题中写明 SGOI9 友谊赛。
射雕英雄外传
话说郭靖和黄蓉在美丽的桃花岛无忧无虑地生活着，花团锦簇，与岛上居民和睦相处，其乐融融！
风云突变，蒙古大军入侵中原，"国家兴亡，匹夫有责"，何况是抱有强烈正义感和爱国精神的郭靖夫妇。他们决定择日动身，前往边关，保家卫国。
情真真，意切切，桃花岛的人们和郭靖夫妇是多么难舍难分！因此，他们决定来举行一次晚会，为郭靖夫妇饯行。
郭靖说："如果你能来参加我们的晚会，并能圆满地完成整个活动，我将会送给你一件精美的礼物！"。不是郭靖的降龙十八掌的套路和黄蓉的打狗棒法吧？太好了，要是我能得到，嘿嘿，我一定能成为……
消息传出，参与者众！有真诚送别的岛上居民，但其中也不乏破坏晚会的敌特分子！
第一幕
为了安全起见，郭靖夫妇租借了一台三维扫描仪器。利用它可以对三维物体(例如大脑)进行扫描，每个参加晚会的人都得经过扫描仪进行识别，其目的就是想通过该扫描仪来分析哪些人带了危险物品（比如炸药和危险兵器）。
扫描仪将扫描的结果用一个三维的数组来保存，数组的每一个元素表示空间的一个象素。数组的元素是0－255的整数，表示该象素的灰度。例如0表示该象素是黑色的，255表示该象素是白色的。
被扫描的物体往往是由若干个部件组合而成的。在实际问题中，同一个部件内部的色彩变化相对连续，而不同的部件的交界处色彩往往有突变。同一个部件内部，相邻两个象素的灰度差不超过正整数M（说明：每一个象素与前后、左右、上下的6个象素相邻）。M决定了程序识别部件的灵敏度。
任务
你必须提供一个scan.exe的可执行程序，对于给定的物体，运行该程序，即刻就可以判断该物体是由几个部件组成的。
输入
在输入的文本文件scan.in中的第一行是三个正整数L,W,H(L,W,H<=50)，表示物体的长、宽、高。第二行是一个整数M（0<=M<=255），表示识别部件的灵敏度。
接下来是L×W×H个0－255的非负整数，按照空间坐标从小到大的顺序依次给出每个象素的灰度。
说明：对于空间两点P1(x1,y1,z1)和P2(x2,y2,z2)，P1<P2当且仅当
(x1<x2)或者
(x1=x2且y1<y2)或者
(x1=x2且y1=y2且z1<z2)
输出
在输出的文本文件scan.out中只有一个整数N，表示一共识别出几个部件。
输入样例
2 2 2
0
1 1 1 1 2 2 2 2
输出样例
2
第二幕
如果通过了三维扫描仪的严格检查，你将能带着你的朋友进入晚会现场，取得了博取郭靖夫妇礼物的机会。
黄蓉真不愧为智多星，在她的策划下，晚会精彩节目层出不穷，高潮不断。
即使是个人的节目，黄蓉也很有创意，将表演和游戏融合起来。她首先选定N*N个客人排成一个边长为N的正方形，表演按照从左至右、从上至下的顺序进行，每个客人都可以表演，也可以观看，如果某个客人表演，则他周围(上,下,左,右,左上,左下,右上,右下)的人都可以观看到他的表演，当表演者表演完毕，则他周围的8个人应该离开，换另外8个人来观看。为了公平起见，如果某个位置是男客离开，则应换女客进来，对应的如果某位置是女客离开，则要换男客进来。
黄蓉提出的问题是：有多少种不同的表演方法能使得最初的N N个客人最后都变成女客。
任务
你必须提供一个game.exe的可执行程序，运行该程序，即刻得到黄蓉的答案。因为答案数目可能巨大，所以黄蓉只要你输出答案对10000求余的结果。
输入
在输入的文本文件game.in中的第一行是一个整数N (2 <= N <= 50)，表示初始客人方阵的大小，接下来N行，每行是一个长度等于N的字串，字符可以是"W"或"M"，"W"表示女客、"M"表示男客。
输出
在输出的文本文件game.out中只有一行，为黄蓉要你回答的结果。
输入样例
5
MMMWW
MWWMM
WWMWM
MWWMM
MMMWW
输出样例
2
第三幕
游戏完毕，接着是智力竞赛。黄蓉首先提出一个问题：如果按性别将客人分为两类，用"W"和"M"分别女客和男客，那么任意N个客人排成一行，有多少种不同的排法？答： 。这么简单啊！降龙十八掌，还有打狗棒法，xixi
! @*^。别高兴得太早了！？黄蓉接着说："个排列中有多少个包含了某个给定的男女排列呢？"
这一下将所有的客人难住了，你能解决吗？
任务
你必须编写一个contest.exe的可执行程序，对于给定的n和给定的男女排列，运行程序contest.exe，即刻得到黄蓉的答案。因为答案数目可能巨大，同样黄蓉只要你输出答案对10000求余的结果。
输入
在输入的文本文件contest.in中的第一行只有一个数n (1≤n≤2000)。第二行是一个由"M"和"W"组成的字符串，表示某个给定的男女排列，长度不超过n。
输出
在输出的文本文件contest.out中只有一行，为黄蓉要你回答的结果。
输入样例
3
MW
输出样例
4
第四幕
游戏结束，接着进入最浪漫的时刻--舞会，"嘣嚓嚓、嘣嚓�"，一对对男女客人双双步入舞池。
舞池的大小只能让m对舞伴同时跳舞，因此每一曲舞中客人们都组成m对舞伴，其余人喝酒聊天等待跳下一曲。我们认为每一对舞伴都是由一男一女组成。
按进场的要求--每一位女客人到来时，都有两位新的男客人陪伴着。我是说，除去黄蓉的每一位女士，因为黄蓉只和郭靖一起来到晚会现场的。
经过统计，知道参加晚会的女客人有n位--包括黄蓉在内。因此，男客人共有2n-1位--包括郭靖在内。
可是，郭靖夫妇很快就发现气氛并不活跃，因为客人们都只和自己认识的同伴跳舞，这样几曲下来，由于女少男多并且很多人互不认识，很多男士就兴趣索然。黄蓉灵机一动，想出了一个主意：给n位女客每人发一张写有编号的卡片，当然，编号是各不相同且都是1 n的整数。这样就可用w[1],
w[2], …, w[n]来表示每位女客。类似的，2n-1位男客每人也发有一张编号是12n-1的卡片，可用m[1],
m[2], …, m[2n-1 ]来表示每位男客。有趣的是，黄蓉总是拿到w[1]这张卡片，而郭靖却不一定能拿到m[1]这张卡片。
为了使得更多的人互相认识，女客w[i]将自己认识的所有男客介绍给w[i+1]，而w[i+1]继续下去，将自己认识的所有男客(包括新认识的)介绍给w[i+2]……
这里的认识定义如下：
如果m[j]是和w[i]一起到来的，则称w[i]认识m[j]；
如果m[j]是w[i-1]介绍给w[i]的，则亦称w[i]认识m[j]。
当然，w[1]不会有人给她作介绍，而w[n]不用给任何人做介绍。
经过这样一番介绍，互相认识的人多了起来，而我们知道：舞会中，凡是互相认识的男女客人都可成为舞伴去跳舞。
黄蓉问你：在经过一番介绍之后，每一曲舞能有多少种不同的舞伴组合方式？
任务
你必须编写一个dance.exe的可执行程序，运行dance.exe即刻得到黄蓉的答案。黄蓉对答案末尾的0不感兴趣，因此你需要把这些0先都去掉。用Y表示把X末尾的0去掉后的数。
你会发现Y可能很大。于是黄蓉只需要你输出Y的后K位数字。当然，如果Y不足K位，就直接输出Y。
如果输出的首位数字也可能是0--她并不想看到这样的输出。于是，请顺便把这些首位的0（如果有的话）也都去掉。
输入
在输入的文本文件dance.in中的第1行有三个整数：n, m, k，1≤m, n, k≤10000，m≤n。第2行一个数，表示郭靖的编号。第3行到n+1行每行两个数，第I行的两个数分别代表陪同w[i-1]到来的两位男客人编号。同一行的数之间由单个空格隔开。
输出
在输出的文本文件dance.out中只有一行，为黄蓉喜欢的答案。
样例
第五幕
"今天你要去远行，送你风雨中….."，伴着凄美的歌声，郭靖夫妇终于踏上征程。为了尽快到达边疆为国效力，他们搭上了2002次列车。可在途径sweet
station时，被该站站长缠住了身，是什么原因呢？
因为该车站由于经营不善，面临破产，该站负责人早闻黄蓉聪明过人，一定要她帮忙出出主意，挽救车站。
该车站有n个车道，由于车道的长度有限，每个车道在某一时刻最多只能停靠一列火车。该站每天将有m列火车从车站经过，其中第i列火车到达车站的时间为Reach[i]，火车上装有价值Cost[i]的货物。
如果该火车进站，则车站将获得Cost[i]的1%收益，但由于货物的搬运时间，该火车将在车站停留一段时间Stay[i]，这段时间内，火车将占用车站中的某一个车道。当然，火车也可以不在站中停靠而直接出站，但这样车站将得不到一分钱。
要挽救车站，就是要对车站的列车进行调度，使获得的效益最大。当然，解决这个问题对于黄蓉来说并不难，但边疆吃紧，时间不等人，你能帮帮黄蓉，让她脱身吗？
任务
你必须编写一个train.exe的可执行程序，运行train.exe即刻得到该站的最大效益。
输入
在输入的文本文件train.in中第1行中为两个正整数：n（n≤20）m（m≤100），第2行到第m+1行，每行有3个不超过1000正整数。第i+1行的3个数分别为：Reach[i]，
Cost[i]和Stay[i]，它们用单个空格分隔。
输出
在输出的文本文件train.out中仅有一行，为车站的最大收益（精确到小数点后2位）。注意，如果火车a从第i车道离开时，火车b刚好到站（即Reach[a]+Stay[a]
=Reach[b]），则它不能进入第i车道。
输入示例
1 3
2 5 1
3 4 1
5 6 2
输出示例
0.11
注：如果你的程序对她的问题的每个测试点都能在时限1秒内解决，你一定会收到一份精美礼品，信不信由你！
|
