SGOI第十次竞赛试题

要求：
　　1、将源程序用WINZIP打包后作为附件发送；
　　2、在邮件主题中注明：SGOI10友谊赛；
　　3、在邮件内容中写明你的：姓名、年段、地区、学校、指导教师和自己的EMAIL地址。
　　　　　　　　　　　　　　　　

古墓丽影之水晶头骨

楔子

　　有些人，只要生命在继续，冒险就在继续，劳拉就是这样一个人，不需要太多的理由，只因为神秘的气息在召唤着她，于是，收拾好行装，她再次踏上征途……

第一幕 奇怪的文章

　　一张信纸摆在劳拉面前，虽然是新的，却散发出一种古老的气味，劳拉皱了皱眉："克里斯叔叔真是的，就算他工作很忙，也不至于把信写的这么简单，他到底发现了什么呢？还是我亲自去他的实验室一趟问个究竟吧！"

　　实验室的门开着，开得很大，透出一丝不安的气息……空无一人？！这一定有问题！劳拉走到克里斯叔叔的电脑旁，希望能从电脑中获得一些有效地信息："都是普通的研究资料……咦，这是什么？"她发现了一篇奇怪的文章，文章全部由英文字符和数字组成，但却拼不出完整的话来，直觉告诉她，这篇奇怪的文章一定包含了重要的信息。经过仔细观察后，劳拉发现这应该是一篇经过加密的文章，加密的方法可能是将原文复制一遍，然后按顺序插入到原文中对应字符之后间隔若干个字符（指原文中的字符）的位置上。不过由于克拉斯叔叔很可能是在匆忙间写下这篇文章的，所以有可能加密的过程并没有完成。另外为了方便验证她的想法，她大胆地假设"若干"个字符不超过9个，且未经加密的字符不超过10个，现在就请你帮忙劳拉分析一下这篇奇怪的文章是否满足她的假设。

任务：

　　你必须提供一个名为article.exe的可执行文件，分析文章是否满足劳拉的猜想。

输入：

　　输入文件的第一行包含一个整数n(n<=50)。以下n行每行为一个长度不超过1000的仅包含大、小写字母的字符串。

输出：

　　输出文件共n行，每行内容为以下3种情况之一：
　　　　1．OK,you are right. （满足劳拉的假设且加密已完成）
　　　　2．I don't know whether you are right. （满足劳拉的假设但加密未完成）
　　　　3．Sorry,I don't think you are right. （假设不满足）
　　如一个字符串同时满足几种情况，则判断的顺序以以上顺序为准。

样例输入(article.in)：

　　3
　　ACABCB
　　ABCAB
　　aa0123456789b

样例输出(article.out)：

　　OK,you are right.
　　I don't know whether you are right.
　　Sorry,I don't think you are right.

第二幕 神秘的锁

　　在你的帮助下，劳拉终于破解了密码，文章的内容却让劳拉有些吃惊："劳拉，如果你看到这封信，那么我大概已经遭遇了不测，但我必须把我的发现告诉你。我根据记载发现了一个玛雅人神殿的位置，据载那是玛雅人举行祭祀的地方，里面收藏有一个价值连城的水晶头骨……""水晶头骨？这大概就是克里斯叔叔失踪的原因了："劳拉喃喃自语道。"看来你已经破解了密码。"劳拉背后响起一个阴郁的声音，她习惯性的一个滚翻，拔枪，射击，一切动作是那么完美，可是对方好像已经预料到她的动作了，这一枪射空了。"别冲动，你的克里斯叔叔还在我们手上呢！"劳拉无奈的放下了枪。"我们相信你的勇气和智慧，用水晶头骨来换你的克里斯叔叔吧！"一个人影一闪，消失在夜幕中。

　　没办法，劳拉开始了新的冒险，依据克拉斯叔叔的指示，她来到位于森林深处的神庙遗址。历经漫长的岁月神庙依然巍然屹立，高大的门显出庄严的气息。门上一把奇异的锁令人感到一种莫名的神秘。锁上有一个槽，槽里从左到右嵌着n个金属片，金属片可以左右移动，但不能离开槽，因此它们的排列次序是不能改变的。根据克里斯叔叔的说法，锁有一个灵异值，而每个金属片也都有一个灵异值。开锁的办法是每次选择两片相邻的金属片，移动并使它们碰到一起，则这两个金属片将自动熔合为一片，且这个新合成的金属片的灵异值等于左边那个金属片的灵异值减去右边那个金属片的灵异值（当然，灵异值可能是负的）。重复这一过程直至只剩下一个金属片，此时，若金属片上的灵异值与锁的灵异值相同，则门自动开启。

　　因为开门的机会只有一次，所以劳拉需要你的帮助。

任务：

　　你必须提供一个名为lock.exe的可执行文件，求出开锁的方法。

输入：

　　输入文件第一行有两个整数n，m（2<=n<=5000,1<=m<=20）。n代表金属片的个数，m代表锁一共有m种可能的灵异值。接下来的n行，第i行的数（1<=<=100）代表从左往右数第i片金属片的灵异值。接下来的m行，每行一个整数，代表锁的一种灵异值。

输出：

　　输出文件分为m组，第i组输出对应当锁的灵异值为时劳拉的开锁过程。对于第i组输出，若灵异值为时锁是可以被打开的，则应该先输出一行"Great！"，接下来的n－1行每行一个数，第j行的数代表第j次劳拉将选择当前从左到右数的第和第＋1片金属熔合；若无论劳拉如何移动金属片，最后都不可能得到灵异值为的金属片，则只输出一行"Impossible！"。

样例输入(lock.in)：

　　4 2
　　2
　　1
　　4
　　3
　　2
　　5

样例输出(lock.out)：

　　Great!
　　2
　　1
　　1
　　Impossible!

第三幕 生死攸关的咒语

　　"吱呀呀"厚重的大门打开了,居然没有那种腐朽的气味,难道因为这里是神殿吗?劳拉有些疑惑不解，"管不了那么多了，还是赶快找到水晶头骨要紧。"她环顾四周，这里虽然很宽敞，却一目了然，空旷的大厅只有一张桌子，上面有许多刻有数字的石板。水晶头骨会在哪儿呢？劳拉走到桌子前，刚想看个究竟，突然，三面墙向她压了过来，同时，一个缥缈的声音在神殿里响起："每个石板上的数字串都是一个咒语元素，用这些咒语元素连接成一条咒语，就可以阻止墙的移动。咒语是由咒语元素连接而成的数字串，且每条咒语至少能用2种不同的连接方法得到，不同的连接顺序可以看成是不同的方法，祝你好运。"

　　在这生死攸关的时刻，劳拉亟需你的帮助，因为时间紧迫，所以她希望你能找出长度最短的咒语。桌子上的石板很多，你可以认为每一种石板都有无数多个。

任务：

　　你必须提供一个名为cantrip.exe的可执行文件，求出长度最短的咒语。

输入：

　　输入文件第一行有一个整数n(2<=n<=200)，以下n行每行为一个长度不超过100的数字串，即n种不同的石板上刻的数字串。

输出：

　　第一行是一个整数，代表你所找到的长度最短的咒语的长度。第二行是你找到的咒语，若有多种拼法使咒语长度最短，则输出按照字典排序最小的一个。数据保证有解。

样例输入(cantrip.in)：

　　4
　　11
　　111
　　00
　　000

样例输出(cantrip.out)：

　　5
　　00000

第四幕 水晶头骨

　　得救了，你成功的找出了咒语，劳拉得救了。桌子陷了下去，露出一段楼梯，劳拉走了下去。终于看到了！神坛上，传说中的水晶头骨闪着幽幽的光，劳拉的心仿佛也被震动了。可是，要想得到它，还不是那么简单，劳拉面前根本没有路！地上布满了地刺，根本无处立足，金属的刺尖泛着蓝光，有毒！劳拉看了看周围，周围有许多高大的柱子，柱子都呈圆柱形，且粗细不一。这些柱子是用某种弹性很好的特殊材料制成的。劳拉发现，任何物体以某一个方向射向柱子后，都将会被反弹出去，"看来借助柱子的弹力是过去的唯一办法。"劳拉自语。

　　由于神坛内有存在一个神秘的场，劳拉的运动将始终处于同一个水平面内。同时，如下图所示，反弹满足反射定律：入射角等于反射角（相对于圆的切线）。

　　　　　　　　　　　　　　　
　
　　如果劳拉最多撞到10个柱子就可以结束弹射，那么她就能够取得那个价值连城的水晶头骨；否则，由于体力消耗过大，她将葬身在这仅与神秘的水晶头骨咫尺之遥的地方！劳拉设想了几种方案，她希望你帮助她判断每一种方案能否成功的在10次之内结束这可怕的弹射。每一种弹射方案包括劳拉的出发点和出发的方向，一旦劳拉出发，她就无法再控制自己的行动，只有任凭自己在柱子之间弹来弹去，所以劳拉希望你能构准确的判断她提出的每一种方案。

任务：

　　你必须提供一个名为escape.exe的可执行文件，判断劳拉的方案是否可行。

输入：

　　每个输入包括多组数据。每组数据的第一行是一个数n，代表有n根柱子，如果n=0，则代表文件结束；接下来的n行，每行三个实数xi，yi，ri，代表第i根圆柱的圆心平面坐标和半径；接着有4个数，表示劳拉在这个方案中设定的出发点和出发方向。

输出：

　　对于每一个计划，首先一行，输出"Plan"和数据的编号。接下来，如果劳拉能够在10次之内结束弹射，则先输出她所碰到的那些柱子的编号，再输出一行"succeed"；如果不能，则输出她碰到的前10根柱子的编号，然后一行输出"fail"。

样例输入(escape.in）：

　　3
　　3 3 2
　　7 7 1
　　8 1 1
　　3 8 1 -4
　　2
　　0 0 1
　　5 0 2
　　2 0 1 0
　　0

样例输出(escape.out)：

　　Plan 1
　　1 2 1 3
　　succeed
　　Plan 2
　　2 1 2 1 2 1 2 1 2 1
　　fail

尾声

　　在你的大力帮助下，劳拉凭借她过人的身手成功得取得了水晶头骨，然而这却只是一个序幕。背着装有水晶头骨的背包，劳拉迈着坚定的步伐，向着阳光走去。