9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

NOI2013团体对抗赛 圈地为王enclosure



第三十届全国信息学奥林匹克竞赛

CCF NOI 2013
团体对抗赛
竞赛时间:2013 年 7 月 19 日上午 8:00-12:00
题目名称 英文名称 输入 输出 每步输出时限 题目类型 圈地为王 Enclosure 标准输入 标准输出 输出每一行之后必须刷新缓冲区 1秒 交互

提交源程序须加后缀:

对于 Pascal 语言 对于 C/C++语言 *.pas *.cpp

注意:最终测试时,所有编译命令均不打开任何优化开关。

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

一、规则说明
0. 故事背景
话说混沌初开之时,人界一片荒芜,此间仅四位神灵肩负着开创天地之命,他们便是 木神句芒、金神蓐收、火神祝融、水神禺疆。然四神使命虽同,神性却各异,故而他们所 开拓的土地只能适宜自己所创子民居住。有鉴于此,四神决定在这洪荒大地上各自组建自 己的部落,名唤『青龙』、『白虎』、『朱雀』、『玄武』,也就是后世的“四大部落”。 但是他们立刻纠结于如何分配土地的问题了。经过旷日持久的商讨,他们终于达成共识, 以同时画地的方式一定乾坤。当然,属性不同的四神在圈地过程中定有所冲突,毕竟即使 为神,定也有点私心……

1. 基本说明
本游戏为多人游戏,地图是 10 * 10 的网格,出生点由玩家自己决定。每人控制一名 角色在 11 * 11 个网格顶点上移动,每回合各角色通过移动和画线的动作来圈出尽可能大 面积的地,同时避免被其他角色杀死。
O x

y

[图 1]

第2页

共 11 页

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

2. 游戏形式与角色动作
本游戏是同步的回合制游戏,每回合所有存活角色通过思考决定此回合的动作,然后 同时做出动作。角色每回合可以做出的动作有: ? 抬笔状态中: ? 向上、下、左、右任意没有阻碍的方向移动一个单位(多个角色可以站在同一顶 点上) ? ? ? ? 落笔,同时向上、下、左、右任意没有阻碍的方向移动一个单位或不动 施放泥缚技能并向上、下、左、右任意没有阻碍的方向移动一个单位(详见后述) 什么都不做

落笔状态中: ? ? 向上、下、左、右任意没有阻碍的方向移动一个单位,但是不能后退 什么都不做

注意,角色每回合的移动不能穿过归属于其他角色的区域内(即“闯入他人领地”), 否则将被判为死亡。角色是可以在任何人的区域的边界上移动的,抬笔状态中也可以进入 自己的区域,但是落笔后不能进入自己的区域。

被“围杀”

误入他人领地而死

[图 2]
第3页 共 11 页

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

3. 圈地
圈地是本游戏的主要目标。角色进入落笔状态后,就会开始画线,即此后角色的运动 轨迹会被记录,并且无法主动退出落笔状态。当且仅当本次的轨迹中出现了闭合区域时, 该角色圈地成功,此闭合区域永久归属该名角色,轨迹消失,所围区域内部所有网格顶点 上的角色死亡(即“被围杀”),同时该角色恢复为抬笔状态。 但在圈地过程中角色是“危险”的,有可能被其他角色中途打断以致死亡。这种情形 包括: ? ? 你的轨迹上出现了其他角色(包括起始点) 你与其他角色碰撞(重叠)

一旦出现这种情形,你的角色立刻死亡,杀死你的角色不会受到影响,除非是同时处 于落笔状态的角色重叠:此时这些重叠的并且处于落笔状态的角色们都会死亡。 ? 特殊情况判定 ? 当你圈地结束的瞬间,如果你所圈区域中已经有被占领的区域,那么你本次所占 的区域是其中的无主部分,注意如果不是连续区域的话会算作多个区域,而且不 同时间占领的区域不能合并。 ? 当你与另外的角色(们)同时圈地结束并且你们所围的区域有交叠,那么结算顺 序是由内向外,也就是说,靠里面的角色获得了圈到的地但是被围杀。(见图 3) ? 当你圈地结束的瞬间,其他角色到了你曾经的轨迹上或与你相撞,那么优先结算 圈地结束的事件,也就是说,你圈地成功,而那个角色也不会受到任何影响。 (见图 4) ? 当多个角色同时打断他人圈地时,同时结算,保证所有打断有效。(见图 5)

第4页

共 11 页

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

其次死亡

首先死亡

[图 3]
圈地成功

[图 4]

[图 5] – 四个角色全部死亡
第5页 共 11 页

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

4. 泥缚
在场的角色具有泥缚技能,只有处于抬笔状态的角色才能使用,具体说明如下: 【技能花费】 10 点得分。 【冷却时间】 无。 【效果】在自己的“身后”,即上一回合所站位置和该位置的两个相邻位置(这两个 位置的连线与上回合给出的行进方向垂直)产生独立的三个泥淖,如果任何角色踩到泥淖, 这个泥淖消失,该角色将会强制在原地停留五回合,意即接下来的五个回合,该角色无论 输出什么动作一律视为不动。可以在其他角色脚下放置泥淖。 【备注】 1. 施放该技能的回合不允许不动。 2. 泥淖持续三回合,第三回合消失并且在这个瞬时踩在原先泥淖上的角色不受影响。 3. 三个泥淖中的一个可能因越界而不能放置,但其余两个不受影响。 4. 泥淖不可叠加,会被最后放置的取代。 5. 多名角色同时踩在同一泥淖上,则都会被束缚。 如果你的角色在落笔时或不动时尝试使用该技能,将会被判死亡。

向右移动并 施放泥缚

被缚

[图 6] – 泥缚的效果

第6页

共 11 页

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

5. 结束条件
当回合开始时场上只剩一名及以下角色存活、游戏总回合数达到 100 或没有无主区 域时,游戏结束,统计各角色所占区域面积来计算得分。 游戏结束时,如果只剩一名角色存活,该名角色将立刻获得所有无主区域,然后计算 得分。

6. 得分的计算
为了促进自己部落之间的交流,自己的土地最好是整块而不是散落各处,所以对于拥 有 n 块区域的角色,得分为


其中 Si 为第 i 块区域的面积,m∈{0, 1, 2, 3}为角色在该场游戏中的编号。

7. 角色致死的所有可能
? ? ? ? ? ? ? ? ? 任意状态 被围杀 任意状态 闯入其他角色领地中 任意状态 试图向地图边界外移动 任意状态 试图在不动时泥缚 落笔状态 轨迹被碰撞 落笔状态 角色被碰撞 落笔状态 进入自己的领地 落笔状态 试图后退、落笔或泥缚 任意状态 程序崩溃、超时、输出非法,或者意外退出

第7页

共 11 页

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

8. 裁判的事件结算顺序(收到所有角色的行动指令后)
? ? ? ? ? ? ? 0、角色输出无法识别的指令或不允许的动作致死 1、角色非法穿越领地与越界移动 2、角色移动 3、角色施放泥缚技能、泥淖因持续回合数满而消失 4、角色踩在泥淖上 5、角色圈地事件与紧接的被围杀事件 6、角色圈地被打断事件

二、输入输出格式
注意:当你输出一行指令后,请使用 flush 或 endl 刷新缓冲区以便控制器接受你的指令

1. 游戏开始时,你的程序将会收到如下一行输入
[START] x x 表示你的角色编号。 例如: [START] 1 你的角色编号为 1。

2. 当你接受到[START]输入后,你的程序需要输出你希望出生在的坐标,格 式如下
[POS] x y x、y 表示你的角色出生坐标,均应该为 0~10 的整数。 例如:

第8页

共 11 页

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

[POS] 0 5 你希望你的角色出生在坐标为(0,5)的顶点上。

3. 在每一回合开始,你的程序会收到如下一行输入表示这个回合开端各个角 色的状态
[STATUS] x0 y0 stat0 trappedleft0 scoredecline0 x1 y1 stat1 trappedleft1 scoredecline1 x2 y2 stat2 trappedleft2 scoredecline2 x3 y3 stat3 trappedleft3 scoredecline3 nTraps trap0x trap0y trap0stat trap1x trap1y trap1stat … 意思是,编号为 i 的角色现在在横坐标为 xi、纵坐标为 yi 的点,状态是 stati,被 束缚剩余回合数为 trappedlefti,技能所耗分数是 scoredeclinei; 场上有 nTraps 个泥淖,第 i 个泥淖坐标为(trapix,trapiy),剩余回合数为 trapistat,不会为 0; 状态为 0 表示抬笔,为 1 表示落笔,为-1 表示死亡。 例如: [STATUS] 2 5 1 0 -20 7 7 0 0 0 7 7 0 1 0 7 7 -1 4 0 3 0 0 1 0 1 1 0 2 1 0 号角色位于(2,5)处已经落笔,1 号、2 号角色都位于(7,7)处抬 着笔,3 号角色死在了(7,7)处;3 号角色刚刚踩到了泥淖,2 号角色 3 回合 前被泥淖束缚;在(0,0)~(0,2)三个点处有三个还剩一回合的泥淖;1 号角 色用过两次泥缚技能。

4. 当接收了[STATUS]输入后,你的程序需要输出本回合的动作,格式如下
[ACTION] direction action

第9页

共 11 页

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

direction 是一个 char,可以是 u(向上),d(向下),l(向左),r(向右), s(不动)中的一个; action 可以是 0(不改变落笔状态),1(要落笔),-1(要施放泥缚技能)中的 一个。 注意落笔以后回合中输出的 action 必须始终为 0,直到角色因占领区域而退出了 落笔状态。 如果你的角色被束缚,该回合你输出的指令会被忽略。 例如: [ACTION] u 1 你希望你所控制的角色落笔,然后向上移动一单位。 [ACTION] s 0 你希望你所控制的角色不动。 [ACTION] r 0 你希望你所控制的角色不改变它的落笔状态,只是向右移动一单位。 [ACTION] r -1 你希望你所控制的抬着笔的角色施放泥缚,在身后放置三个泥淖。

5. 样例(四人游戏)
(judge >> i 表示裁判向 i 号角色输入信息,i >> judge 表示 i 号角色向裁判输出信息)
类别 judge >> 0 0 >> judge judge >> 1 内容 [START] 0 [POS] 9 3 [START] 1
第 10 页 共 11 页

第三十届全国信息学奥林匹克竞赛

团体对抗赛 圈地为王

1 >> judge judge >> 2 2 >> judge judge >> 3 3 >> judge judge >> 0 0 >> judge judge >> 1 1 >> judge judge >> 2 2 >> judge judge >> 3 3 >> judge judge >> 0 0 >> judge judge >> 1 1 >> judge judge >> 2 2 >> judge judge >> 3 3 >> judge judge >> 0 0 >> judge judge >> 1 1 >> judge judge >> 2 2 >> judge judge >> 3 3 >> judge …

[POS] 1 6 [START] 2 [POS] 0 3 [START] 3 [POS] 4 5 [STATUS] 9 [ACTION] l [STATUS] 9 [ACTION] s [STATUS] 9 [ACTION] r [STATUS] 9 [ACTION] s [STATUS] 8 [ACTION] l [STATUS] 8 [ACTION] l [STATUS] 8 [ACTION] r [STATUS] 8 [ACTION] s [STATUS] 7 1 7 2 [ACTION] l [STATUS] 7 1 7 2 [ACTION] r [STATUS] 7 1 7 2 [ACTION] l [STATUS] 7 1 7 2 [ACTION] r …

3 0 0 3 0 0 3 0 0 3 0 1 3 0 0 3 0 -1 3 0 0 3 0 0 3 0

0 0 1 6 0 0 0 0 3 0 0 0 4 5 0 0 0 0 0 0 1 6 0 0 0 0 3 0 0 0 4 5 0 0 0 0 0 0 1 6 0 0 0 0 3 0 0 0 4 5 0 0 0 0 0 0 1 6 0 0 0 0 3 0 0 0 4 5 0 0 0 0 0 0 1 6 0 0 0 1 3 0 0 0 4 5 1 0 0 0 0 0 1 6 0 0 0 1 3 0 0 0 4 5 1 0 0 0 0 0 1 6 0 0 0 1 3 0 0 0 4 5 1 0 0 0 0 0 1 6 0 0 0 1 3 0 0 0 4 5 1 0 0 0 0 0 0 6 0 0 -10 2 3 0 0 0 4 5 1 0 0 3 1 5 2 1 6 2

0 3 0 0 0 0 6 0 0 -10 2 3 0 0 0 4 5 1 0 0 3 1 5 2 1 6 2 1 3 0 0 0 0 6 0 0 -10 2 3 0 0 0 4 5 1 0 0 3 1 5 2 1 6 2 1 3 0 0 0 0 6 0 0 -10 2 3 0 0 0 4 5 1 0 0 3 1 5 2 1 6 2 0

第 11 页 共 11 页



更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图