第一题  拳皇2003（kof.exe  TimeLimit: 5s  10点/100分）

SNK公司的拳皇(King of the fighter)相信大家都玩过。高手的话，半夜拉他起来也能把出招表倒背如流，并且可以闭着眼睛在摇秆上耍出来。所以SNK公司希望拳皇的新版本——拳皇2003的出招表能够仅可能的难记住并且难练出来。

如右图所示，我们可以把一个出招的方式看作一连串的表示方向的代码按顺序组成的字符串（E、S、W、N分别表示右、下、左、上）。比如出招方法“WSEWSE”就是表示要出此招必须要按顺序在摇杆上摇6次，分别是：向左、向下、向右、向左、向下、向右。

为了不让玩家能够过与容易记住和练出这些招术，SNK公司想出了一些出招方法。SNK公司认为，如果一个出招方法中含有两个或者两个以上的连续出现子串，那么这个出招方法就很容易记住，比如：WSEWSE、SS、EWSWSN、EES。如果没有连续两个连续出现的子串，那么这个出招方法就比较难记住，比如：WSENSEW、SW、SWS。

现在SNK公司给一个长度在1到100之内的出招方法给你，要你判断它是容易记住的出招方法还是难记住的出招方法。如果是容易记住的出招方法，请输出它的最长的连续出现的子串；否则就输出“diff”。

 

输入文件：仅一行，既给定的出招方法，长度在1到100之内。

 

输出文件：仅一行。如果是容易记住的出招方法，请输出它的最长的连续出现的子串（如果有多个最长的子串，请输出最先出现的最长的子串）；否则就输出“diff”。

 

样例：

 

(1)

kof.in

WEENNENNES

kof.out

ENN

 

(2)

kof.in

WESNSEW

kof.out

diff

 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - -

第二题  仙剑奇侠传之仙灵岛（pal.exe  Timelimit: 5s 10点/100分）

    话说李逍遥救婶婶心切，决定独自一人闯入仙灵岛的迷幻阵，寻找通往水月宫的路，希望仙女能够赐药救活婶婶。李逍遥足不停步的向南走去，忽觉云雾缭绕景色晃动，只有荷叶组成的路在水面晃动，剎那间身陷恍惚之境，峰回路转，时时变幻，岛上禁制已然暗自发动。逍遥心里一慌，急于脱困见路就走，可是眼前景色时幻时灭，走了许久也不知自己身在何方，使得逍遥头晕目眩。李逍遥不仅一慌：若不快走出这幻境，婶婶岂不是没救了？！

李逍遥勇救亲人之举感动了上天。于是，上天便赐予他一张迷幻阵的地图，并且留给他一句话：“图中有T尊神像，请务必将其全部击破，方可出阵。此地荷叶即过即沉，且万不可走回头之路！”

地图为一个n*m的矩阵(1<=n,m<=20)，用map[I , J] 表示每一个地点的情况。Map[I , J]可能有6种情况：

(1)   为“W”，说明这点是荷叶构成的固定的路，可以通过。

(2)   为“X”，说明这点是湖的一部分，不能通过。

(3)   为0到9的数字，说明这点是一个浮动的荷叶，可以通过荷叶瞬间漂到到另外一个数字相同的点（数字点总是成对的出现，如果地图一点为3，必定有另外一点也为3，并且不会出现两个浮动的荷叶连在一起的情况）。

(4)   为“G”，说明这点是神像，到这点时就可以击破改神像，并且可以通过。

(5)   为“B”，说明这点是李逍遥开始的位置，这点为一个荷叶路。

(6)   为“E”，说明着点是打开通往水月宫之路的目的点（如果神像都打破了的话），这点为一个荷叶路。

李逍遥想了想，决定还是请您帮他找到一条所需要时间最少的路，以最快的速度找到水月宫，拿回仙药救活他的婶婶。他每移动一次需要1个时间单位，击破一个神像需要2个时间单位（可以看成击破神像需要1个时间单位，并且通过该点也要1个时间单位）。并且我们知道绝对有一条以上的路可以通往水月宫。请您快想办法帮帮他吧！

 

 

输入文件：第一行，前两个数字为n、m (3<=n,m<=10)，后面的一个为t (0<=t<=10)

         第2行到第n+1行为地图内对应的每点map[I , J]。

 

输出文件：仅一行，既他击破所有的神像并且到达目的点的最少花费的时间。

 

样例：

pal.in             pal.out

5 5 1              7 

WXWW0         （即 (2,1) -> (2,2)=(1,5) -> (2,5)=(5,3) -> (4,3) -> (4,2)

B0WX1            -> (5,2) -> (5,1) ）
XXWXX

XGWWX

EW1WW

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - -

第三题 反恐精英 （cs.exe  TimeLimit: 5s  10点/100分）

Counter Strike警察Fruit正在和匪徒们展开激烈的搏斗。但是匪徒们火力太强大，同伴都受伤了。在这关

A 狙击枪 最多10颗子弹 D沙漠之鹰 最多7颗子弹 M 冲锋枪 最多30颗子弹 B 手雷 最多1个

键时刻，Fruit必须使出自己的看家本领，依靠个人的力量消灭这些狂妄的匪徒。但是，Fruit所能用的武器和弹药十分有限，很有可能不能将匪徒们全部消灭掉。所以Fruit想利用有限的弹药，使消灭的匪徒人数最多。

对方匪徒有n(1<=n<=100)个人，但是他们有些也可能受了伤。我们用ti(1<=i<=n)来表示每一个匪徒的生命值(生命值为整数，最多为100，如果生命值小于或者等于0，那么我们认为这个匪徒已经死了。我们认为开始匪徒都还活着)。

武器分为4种，分别为AWP(狙击枪，用A代表，最多有10颗子弹)、MP5(冲锋枪，用M代表，最多30颗子弹)、Desert Eagle(沙漠之鹰手枪，用D代表，最多7颗子弹)和BOMB(手雷，用B代表，最多1枚)。一个武器的杀伤力，就是指这个武器一次攻击的对它的目标的生命值的损害度，比如100的生命值匪徒，被一个杀伤力为30的武器攻击一次，他就只剩70的生命值。AWP的杀伤力为99点，每次作用于一个人。MP5的杀伤力为25点，每次作用于一个人。Desert Eagle的杀伤力为40点，每次作用于一个人。BOMB有些不同。虽然BOMB的杀伤力为50点，每次作用于一个人，但是，由于它威力很大，所以其他人还是会受到10点的伤害（BOMB投向的那个已经受到50点伤害的人不在内）。Fruit的枪法和投掷都非常的准，理论上是不会出现没打中的情况的。

情况很紧急，容不得半点拖延。你就是这位英勇的警察，赶快开动脑筋，消灭这些匪徒吧！

 

 

输入文件：第一行为匪徒的总人数n(1<=n<=100)，第2行到第n+1行为每个匪徒的生命值ti(1<=I<=n，1<=ti<=100)。第n+2行为拥有的武器数量m(0<=m<=4)。第n+3到n+m+3行的一个字母表示武器的种类，后面的数字为该种武器的弹药数。

 

输出文件：仅一行。输出最多能够消灭几个匪徒。

 

样例：

cs.in

5

100

10

30

1

25

4

A 0

M 1

D 2

B 1

 

cs.out

4

 

 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - -

第四题 星际争霸 （sc.exe  TimeLimit: 5s  10点/100分）

在星际争霸这款游戏中，布兵（就是选择自己的士兵各自的位置）的

（图一）

方法是非常重要的。假设我们有t个士兵，他们处在一个n*m的地图上，并且各自有一个坐标(xi,yi) (1<=I<=t)来表示他们在地图上的位置（右下脚的坐标为(1,1)）。他们各自手持的武器可能不一样，所以会有不同的射程si。我们可以用一个边长为2i+1矩阵来表示他的武器射程的覆盖范围，中心便是他的位置，如图一：黑点为一个士兵，他的坐标是(x,y)，他的射程是3，那么黄色的部分就是他的武器射程的覆盖范围（不包括他本身所在的点）。

但是为了能够袭击更多的敌人，我们希望这个总覆盖范围能够最大。如果出现多个士兵的射程覆盖范围重合的情况，重合部分我们只算一次。

问题是，给定每个士兵的位置以及他的射程，求在整个地图范围内，武器射程的最大总覆盖面积。

 

输入文件： 第一行有三个整数，分别是n、m、t ( 0<=t<=100, 1<=n,m<=10000 )

           第2行到第2+t行，每行有三个数，分别是第I个士兵的xi、yi、si（1<=I<=t，1<=xi<=n，1<=yi<=m，1<=si<=100）

 

输出文件： 仅一行，即武器射程的最大总覆盖面积。

 

样例：

 

sc.in

100 100 3

1 1 5

1 5 3

50 50 1

sc.out

53