SGOI第四次竞赛试题
　　　　　　　　　　　　　　第二试

说明：

　　1. 7月28日(星期六)上午8：00至12：00在中国曙光教育网-"信息学奥赛"专栏上公布第一试题目; 7月29日(星期日)上午8：00至12：00公布第二试题目，参赛者可下载题目，并作答。
　　
　　2. 本次竞赛采用黑闸子测试，参赛者必须严格按照试卷中要求的程序名、输入/出文件名及格式，进行作答。 　
　
　　3. 参赛者必须在当日16：00前将所有解答（.pas）及参赛者信息等文件用Winzip压缩，Email给sgoi@shuguang.net 收,并在邮件的主题中写明SGOI4友谊赛。
　　
　　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 中共有两行，第一行包含一个数n(1<=n<=20),表示牌的张数。第二行有N个数依次为各张牌的点数，每个数为1~10的整数，以空格分开。

输出数据：　　
　　　　 输出文件puzzle.out 中仅有一个数为M的最大值．

输入输出样例：