2452. sunny的宠物

单点时限: 2.0 sec

内存限制: 256 MB

众所周知,经济危机正在席卷全球,而 sunny 也毫无例外的给席卷了,为了缓解经济问题,sunny 准备做宠物买卖!

sunny 买了 N 只小老鼠(俗名耗子)!他给每只耗子取了一个唯一的名字 name,而且每只耗子有一个体力值 power!自从有了宠物,sunny 整个成了一宠物保姆(没办法,谁叫咱遇上了经济危机了呢)!

每天喂耗子们吃饭是一件痛苦的事情,因为 sunny 寝室空间有限,所以只能容下边长为 M 的正方形餐桌,sunny 把这张餐桌分成了 M*M 个喂食的地方,每个地方有一个唯一的坐标 (x,y),表示 x(从上到下) 行 y(从左到右) 列的交点!行列编号都从 0 开始!而你的任务就是模拟 sunny 喂食的过程!

喂食开始后,餐桌上开始都没有耗子,所有的耗子都处于无领地状态!sunny 只发出三种指令:

  • Dispatch A to x y 意味着把名字为 A 的耗子派到位置为 (x,y)(0<=x,y
  • 如果 powerA>powerB,则 A 呆在 (x,y) 处,B 则沿着如下图所示的线路从相距 (x,y) 为 1,2,k,k+1……的周边上寻找空位! 相距为 k 的周边是这样定义的:起点为 (x,y) 的第 k 个左斜上方,顺时针环绕成为一个封闭的正方形!如果起点不在合法范围内,则遍历这个周边直到第一个合法的位置出现,则该处为起点,如果遍历完之后还没有发现一个合法的位置,则寻找结束! 如果存在一个合法位置为空位,则 B 就呆在该处,指令结束!若直到寻找结束仍然没有发现空位,则 B 将处于无领地状态,同时将 B 的 power 加上 1,指令结束
  • powerA<=powerB,则 B 呆在原地,A 沿着以上规则寻找空位,若找到则呆在该处,指令结束! 若直到寻找结束仍然没有发现空位,则 A 将处于无领地状态,同时将 A 的 power 加上 1,指令结束!
若 A 在以上规则下不于无领地状态,则输出”Success!”, 否则输出”Fail!”(引号不输出,下同)。 假设现在的餐桌为下图 1!若 A 被指派到 (2,2),则可看到该处已经有名为 Mouse 体力值为 12 的耗子,若 A 的体力值小于等于 12,则 A 将沿着红线寻找空位,黄色区域代表每次的起点,每条红线代表距 (2,2) 为 k(1,2,……) 的周边!同理可得图 2
  • Who x y 意味着询问 (x,y) 处的耗子的名字! 如果该处没有耗子,则输出”There is empty!”! 否则输出”The place is occupied by A!” A 为该处耗子的名字
  • Where A 意味着询问名字为 A 的耗子在什么地方! 如果 A 在 (x,y) 处,则输出”A is in the place (x,y)!”! 如果 A 处于无领地状态,则输出”A is free!”
  • 输入格式

    第一行为一个整数 T(0<T<=20), 代表有 T 组测试数据!

    对于每组数据:

    第一行为两个数 N(1<=N<500),M(2<=M<20),分别代表 sunny 家的耗子数和 sunny 寝室餐桌的边长!

    第二行为 N 个长度不超过 10 的不同字符串,name1,name2,……nameN, 分别代表 N 只耗子的名字!字符串由字母 (‘a’-‘z’,’A’-‘Z’) 组成,并且中间无空格!

    第三行为 N 个整数 (0~1000),power1,power2,……powerN, 分别代表 N 只耗子的体力值!

    接下来每行一条命令,分别为以上三条之一!最后一行命令为”OVER”,意味着喂食结束,不要求处理!

    输出格式

    对于每条指令,参照上面说明输出对应的信息!

    样例

    Input
    1
    5 2
    MdgWGJOLz NblOmku KSXJE mHpAqCk sKPKLxq
    760 454 701 316 423
    Where MdgWGJOLz
    Who 1 1
    Who 1 1
    Dispatch MdgWGJOLz to 0 0
    Dispatch mHpAqCk to 0 1
    Dispatch NblOmku to 0 0
    Where sKPKLxq
    Who 0 1
    Where mHpAqCk
    Who 1 0
    OVER
    
    Output
    MdgWGJOLz is free!
    There is empty!
    There is empty!
    Success!
    Success!
    Success!
    sKPKLxq is free!
    The place is occupied by mHpAqCk!
    mHpAqCk is in the place(0,1)!
    There is empty!
    

    3 人解决,16 人已尝试。

    6 份提交通过,共有 165 份提交。

    9.4 EMB 奖励。

    创建: 11 年,9 月前.

    修改: 3 年前.

    最后提交: 6 年,11 月前.

    来源: 2008年选拔赛

    题目标签