曙光信息学奥林匹克第4次友谊赛试题第二试.doc

SGOI第四次竞赛试题第二试说明：1. 7月28日(星期六)上午8：00至12：00在中国曙光教育网-信息学奥赛专栏上公布第一试题目; 7月29日(星期日)上午8：00至12：00公布第二试题目，参赛者可下载题目，并作答。2. 本次竞赛采用黑闸子测试，参赛者必须严格按照试卷中要求的程序名、输入/出文件名及格式，进行作答。 3. 参赛者必须在当日16：00前将所有解答（.pas）及参赛者信息等文件用Winzip压缩。 4. 参赛者信息文件包括：参赛者所在省、市、学校、年级、真实姓名、指导教师、联系地址、指导教师的电子邮件。 5. 主办单位于7月28日下午18:00开始第一试测试、7月29日下午18:00始第二试测试，8月2日上午9：00在中国曙光教育网上公布参赛者成绩，随后将参赛者优秀的解答、测试数据、参考解答和解题报告，以学校为单位发给指导教师并在中国曙光教育网上公布。（注：若参赛者采用C语言或Qbasic语言参赛，请将对应程序的可执行文件（.exe）提交上来） 试题1. 彩灯布置 (A.pas) 题目叙述： 为了庆祝北京申奥成功,X市决定举行一次规模宏大的联欢晚会设计师om被邀请负责晚会的灯光设计 晚会舞台的正上方有n盏可以任意变换颜色的彩灯它们排列成规则的圆形为了增加舞台的美感，om决定将任意两盏相邻彩灯设计成不同的颜色因为演出时还要随时变换彩灯的颜色，所以Tom必须设计出多种方案（只要有一盏对应的彩灯颜色不同，就算两种不同的方案）。 于是一个棘手的问题摆在Tom面前：若有m种颜色，n个彩灯，那么不同的设计方案有多少种呢？因为当n,m较大时，方案数太多，因此他需要你的帮助 注意：因为每一盏彩灯的位置固定，所以经过旋转或翻转能重合的也算不同的方案输入数据： 输入文件igths.in 中共有一行，两个数：n,m,依次为彩灯的个数与颜色总数（1=n=100,1=m=100） 输出数据： 输出文件Lights.out 中仅有一个数为方案总数 输入输出样例： 试题2.迷宫 （B.pas ）问题描述： Tom率领着一支探险队在沙漠中无意发现了一座古代文明留下的迷宫，为了抢在别的探险队到来之前了解迷宫中的奥秘，Tom决定冒险走一次迷宫。 Tom的队友在迷宫周围发现了一张地图，地图上记载：迷宫分为n行m列共n*m个方格，每个方格可能是空地或障碍物，迷宫的四周是墙；在其中一个空地中放置着一个开关和一本圣书，开关控制着迷宫中的k个魔鬼，圣书则是Tom想要的。迷宫中的魔鬼都是杀人不眨眼的猛兽，战胜他们的唯一办法就是关闭迷宫中的一个开关。迷宫只有一个入口，进出都只能经过这个入口。 一旦有人进入迷宫，迷宫会在t秒内自动毁灭，迷宫中一切都将消失（包括魔鬼和迷宫中的人）。Tom想知道他能否在迷宫毁灭之前得到圣书、消灭魔鬼并安全离开。 第i个魔鬼第一时刻处在第i1行第i2列，面朝北。在某一时刻，如果魔鬼面前是障碍或墙，则它顺时针转90度；否则它将向前走一格。魔鬼向前走一格或转90度所需的时间均为1秒。 人在某一时刻可以向东西南北任一个空地走一格或原地不动，(人转身不需要时间)，耗时为1秒钟。若某一时刻人和一个魔鬼在同一个格子里，则人会被吃掉。当Tom走到有开关和圣书的格子里，如果格子里没有魔鬼，他就可以得到圣书并关闭所有魔鬼的开关，否则他将被吃掉。（注：当出现类似以下情况时，人不会被吃掉）输入格式： 输入文件名为maze.in， 第一行为n，m，k，t， 以后n行每行m个字符描述迷宫的结构，#为障碍物，.为空地，K表示有开关和圣书的格子（也是空地）。 紧跟着k行，每行有两个数，描述这个魔鬼初始时所在的行和列。初始时所有魔鬼面朝北。 最后一行有两个数，描述唯一的入口所在的行和列。 输出格式： 输出文件名为maze.out 仅有一个数，表示最少需要的时间。如果不能完成任务并及时离开，则输出0。数据范围： 输入样例： 输出样例： 12 (注意：1、拿到圣书后要尽快离开迷宫，否则前面的努力就白费了！ 2、如果你的程序只对特殊情况作判断，将不能得分） 试题3.外公的难题 (C.pas) 题目叙述： Happy老爷爷的外孙Jacky能写会算，聪明绝顶，老爷爷非常喜欢他。Jacky最喜欢算24点了，可是因为他的知识还不够，他只会做加法，减法和乘法，另外也会使用括号。这次外公给他出了一道难题：从N张牌中任选若干张分成M墩( 每墩不超过5张牌)，使得每墩的各张牌都可以算出24点。这本来并不困难，但是外公又要求M的值最大，这可难坏了小Jacky。你愿意帮帮他吗？ 输入数据：输入文件puzzle.in 中共有两行，第